출처: [2020 카카오 인턴] 수식 최대화

문제

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다.
이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다.
해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

1

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.
대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

제한

• expression은 길이가 3 이상 100 이하인 문자열입니다.

• expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(

  1

  +, -, *

  ) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.

  • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.

• expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.

  • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
  • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.

• expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.

• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.

• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

입출력

입출력 예 1

* > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.
100-200*300-500+20
= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420
따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.

입출력 예 2

- > * 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.(expression에서 + 연산자는 나타나지 않았으므로, 고려할 필요가 없습니다.)
50*6-3*2
= 50*(6-3)*2
= (50*3)*2
= 150*2
= 300
따라서, 우승 시 받을 수 있는 상금은 300 입니다.

풀이

• 식에서 사용 된 연산자

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

from itertools import permutations
import re

def solution(expression):
    expressions = set(re.findall("\D", expression))
    prior = permutations(expressions)
    result = []

    for op_prior in prior:
        temp = re.compile("(\D)").split('' + expression)
        for exp in op_prior:
            while exp in temp:
                idx = temp.index(exp)
                temp = temp[:idx - 1] + [str(eval(''.join(temp[idx - 1:idx + 2])))] + temp[idx + 2:]
        result.append(abs(int(temp[0])))
    return max(result)

'''
if __name__ == "__main__":
    expression_list = ["100-200*300-500+20", "50*6-3*2"]
    result_list = [60420, 300]

    length = len(result_list)

    for i in range(length):
        answer = solution(expression_list[i])
        if answer == result_list[i]:
            print('{}번 정답입니다.'.format(i + 1))
        else:
            print('{}번 실패입니다.'.format(i + 1))
            print('{} != {}'.format(answer, result_list[i]))
'''

출처: [2020 카카오 인턴십] 키패드 누르기

문제

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

제한

• numbers 배열의 크기는 1 이상 1,000 이하입니다.

• numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.

• hand는

  1

  "left"

  또는

  1

  "right"

  입니다.

  • "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.

• 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

입출력

입출력 예 1

순서대로 눌러야 할 번호가 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]이고, 오른손잡이입니다.

따라서 "LRLLLRLLRRL"를 return 합니다.

입출력 예 2

왼손잡이가 [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]를 순서대로 누르면 사용한 손은 "LRLLRRLLLRR"이 됩니다.

입출력 예 3

오른손잡이가 [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]를 순서대로 누르면 사용한 손은 "LLRLLRLLRL"이 됩니다.

풀이

• 각 번호를 좌표로 만들고, 두 점 사이의 거리를 이용한다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def solution(numbers, hand):
    number_coord = [(3, 1), (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
    left_hand = (3, 0)
    right_hand = (3, 2)
    answer = ''

    for number in numbers:
        if number in [1, 4, 7]:
            answer += 'L'
            left_hand = number_coord[number]
        elif number in [3, 6, 9]:
            answer += 'R'
            right_hand = number_coord[number]
        elif number in [2, 5, 8, 0]:
            # 다음 pos의 좌료와 현재 양손의 좌표사이의 거리 구하기
            next_x, next_y = number_coord[number]
            left_x, left_y = left_hand
            right_x, right_y = right_hand
            # abs(x_h - x_n) + abs(y_h - y_n)

            left_distance = abs(next_x - left_x) + abs(next_y - left_y)
            right_distance = abs(next_x - right_x) + abs(next_y - right_y)
            if left_distance < right_distance:
                answer += 'L'
                left_hand = number_coord[number]
            elif left_distance == right_distance:
                if hand == 'right':
                    answer += 'R'
                    right_hand = number_coord[number]
                else:
                    answer += 'L'
                    left_hand = number_coord[number]
            else:
                answer += 'R'
                right_hand = number_coord[number]
    return answer

출처: [백준] 10844번 쉬운 계단 수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

1

1

예제 출력 1

1

9

예제 입력 2

1

2

예제 출력 2

1

17

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 다이나믹 프로그래밍

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import sys

input = sys.stdin.readline

dp = [[1 for _ in range(10)]]
for i in range(99):
    dp.append([0 for _ in range(10)])

for i in range(99):
    for j in range(10):
        if 1 <= j < 9:
            dp[i + 1][j] = dp[i][j - 1] + dp[i][j + 1]
        elif j >= 9:
            dp[i + 1][j] = dp[i][j - 1]
        elif j <= 0:
            dp[i + 1][j] = dp[i][j + 1]
# print(dp)
n = int(input())
print((sum(dp[n - 1]) - dp[n - 1][0]) % 1000000000)

출처: [백준] 1436번 영화감독 숌

문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, …. 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

예제 입력 1

1

2

예제 출력 1

1

1666

힌트

출처

• 문제를 번역한 사람: baekjoon
• 어색한 표현을 찾은 사람: mwy3055

알고리즘 분류

• 브루트포스 알고리즘

시간 제한

풀이

• 666,1666,2666,3666,4666,5666,6660,6661…….

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import sys

input = sys.stdin.readline

N = int(input())

title = 666
cnt = 0
while True:
    if '666' in str(title):
        cnt += 1
        if cnt == N:
            print(title)
            break
    title += 1

출처: [백준] 2447번 별 찍기-10

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, …)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

1
2
3

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

예제 입력 1

1

27

예제 출력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

힌트

출처

• 문제를 만든 사람: baekjoon
• 문제를 다시 작성한 사람: jh05013

알고리즘 분류

• 분할 정복
• 재귀

시간 제한

풀이

• 1, 4, 7, 10, 13, 16, 19, 22, 25 …. 3으로 나눈 나머지가 1인 부분이 공백
• 전체를 봤을때, 3줄씩 한 세트라고 하면, 3, 4, 5, 12, 13, 14, 21, 22, 23…. (n//3)%3==1인 부분이 공백

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import sys

input = sys.stdin.readline

N = int(input())
arr = [['*'] * N for _ in range(N)]  # output array 생성

temp = N
cnt = 0
while temp != 1:  # 입력받은 n이 3의 몇승?
    temp /= 3
    cnt += 1


'''
1, 4, 7, 10, 13, 16, 19, 22, 25 .... 3으로 나눈 나머지가 1인 부분이 공백
전체를 봤을때, 3줄씩 한 세트라고 하면, 3, 4, 5, 12, 13, 14, 21, 22, 23....  (n//3)%3==1인 부분이 공백
'''
for i in range(cnt):
    idx = []
    for j in range(N):
        if (j // 3 ** i) % 3 == 1:
            idx.append(j)
    for row in idx:
        for col in idx:
            arr[row][col] = ' '

print('\n'.join([''.join([str(i) for i in row]) for row in arr]))

출처: [백준] 1018번 체스판 다시 칠하기

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 88 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8x8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8x8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
9

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1

1

1

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

예제 출력 2

1

12

힌트

출처

• 문제를 번역한 사람:
• 데이터를 추가한 사람:
• 문제를 다시 작성한 사람: jh05013

알고리즘 분류

• 브루트포스 알고리즘

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
board = [list(input().rstrip()) for _ in range(N)]


def check_BW(slice_board):
    # print(slice_board)
    black_cnt = 0  # black 시작 [bwbwbwbw],[wbwbwbwb]
    for row in range(8):
        for col in range(8):
            if (row % 2 == 0 and col % 2 == 0) or (row % 2 == 1 and col % 2 == 1):
                if slice_board[row][col] != "B":
                    black_cnt += 1
            if (row % 2 == 0 and col % 2 == 1) or (row % 2 == 1 and col % 2 == 0):
                if slice_board[row][col] != "W":
                    black_cnt += 1

    white_cnt = 0  # white 시작 [wbwbwbwb],[bwbwbwbw]
    for row in range(8):
        for col in range(8):
            if (row % 2 == 0 and col % 2 == 0) or (row % 2 == 1 and col % 2 == 1):
                if slice_board[row][col] != "W":
                    white_cnt += 1
            if (row % 2 == 0 and col % 2 == 1) or (row % 2 == 1 and col % 2 == 0):
                if slice_board[row][col] != "B":
                    white_cnt += 1

    return min(black_cnt, white_cnt)


check = []
for row in range(N - 7):
    for col in range(M - 7):
        cnt1, cnt2 = 0, 0
        # 체스판 경우의 수 slicing
        c = [board[row + i][col:col + 8] for i in range(8)]
        # c = [c[(0 + col):(8 + col)] for c in board[(0 + row):(8 + row)]]
        check.append(check_BW(c))
print(min(check))

출처: [백준] 18869번 멀티버스Ⅱ

문제

M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, …, AN, 우주 B에 있는 행성의 크기는 B1, B2, …, BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.

• Ai < Aj → Bi < Bj
• Ai = Aj → Bi = Bj
• Ai > Aj → Bi > Bj

입력

첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.

출력

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.

제한

• 2 ≤ M ≤ 100
• 3 ≤ N ≤ 10,000
• 1 ≤ 행성의 크기 ≤ 1,000,000

예제 입력 1

1
2
3

2 3
1 3 2
12 50 31

예제 출력 1

1

1

• (A, B) = (1, 2)
  • A1 = 1 < A2 = 3 이고, B1 = 12 < B2 = 50
  • A1 = 1 < A3 = 2 이고, B1 = 12 < B3 = 31
  • A2 = 3 > A3 = 2 이고, B2 = 50 > B3 = 31
• 모든 1 ≤ i, j ≤ N에 대해서 만족한다.

예제 입력 2

1
2
3

2 3
1 3 2
12 50 10

예제 출력 2

1

0

• (A, B) = (1, 2)
  • A1 = 1 < A3 = 2 인데, B1 = 12 > B3 = 10이다.
• 모든 1 ≤ i, j ≤ N에 대해서 만족하지 않는다.

예제 입력 3

1
2
3
4
5
6

5 3
20 10 30
10 20 60
80 25 79
30 50 80
80 25 81

예제 출력 3

1

2

• 1번과 5번 우주, 2번과 4번 우주가 균등하다.

힌트

출처

• 데이터를 추가한 사람: akaishuichi
• 문제를 만든 사람: baekjoon

알고리즘 분류

• 정렬
• 값 / 좌표 압축

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import sys

input = sys.stdin.readline

M, N = map(int, input().split())

space_list = [list(map(int, input().split())) for _ in range(M)]

new_space_list = [[] for _ in range(M)]
dictionary = {}
for i in range(M):
    new_list = sorted(list(set(space_list[i])))
    for j in range(len(new_list)):
        dictionary[new_list[j]] = j
    for x in (space_list[i]):
        new_space_list[i].append(dictionary[x])

new_space_list.sort()
cnt, ans = 1, 0
for i in range(1, M):
    if new_space_list[i] == new_space_list[i - 1]:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        cnt = 1

ans += cnt * (cnt - 1) // 2
print(ans)

출처: [백준] 18868번 멀티버스Ⅰ

문제

M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, …, AN, 우주 B에 있는 행성의 크기는 B1, B2, …, BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.

• Ai < Aj → Bi < Bj
• Ai = Aj → Bi = Bj
• Ai > Aj → Bi > Bj

입력

첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.

출력

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.

제한

• 2 ≤ M ≤ 10
• 3 ≤ N ≤ 100
• 1 ≤ 행성의 크기 ≤ 10,000

예제 입력 1

1
2
3

2 3
1 3 2
12 50 31

예제 출력 1

1

1

• (A, B) = (1, 2)
  • A1 = 1 < A2 = 3 이고, B1 = 12 < B2 = 50
  • A1 = 1 < A3 = 2 이고, B1 = 12 < B3 = 31
  • A2 = 3 > A3 = 2 이고, B2 = 50 > B3 = 31
• 모든 1 ≤ i, j ≤ N에 대해서 만족한다.

예제 입력 2

1
2
3

2 3
1 3 2
12 50 10

예제 출력 2

1

0

• (A, B) = (1, 2)
  • A1 = 1 < A3 = 2 인데, B1 = 12 > B3 = 10이다.
• 모든 1 ≤ i, j ≤ N에 대해서 만족하지 않는다.

예제 입력 3

1
2
3
4
5
6

5 3
20 10 30
10 20 60
80 25 79
30 50 80
80 25 81

예제 출력 3

1

2

• 1번과 5번 우주, 2번과 4번 우주가 균등하다.

힌트

출처

• 데이터를 추가한 사람: akaishuichi
• 문제를 만든 사람: baekjoon

알고리즘 분류

• 브루트포스 알고리즘
• 정렬

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import sys

input = sys.stdin.readline

M, N = map(int, input().split())

space_list = [list(map(int, input().split())) for _ in range(M)]

new_space_list = [[] for _ in range(M)]
dictionary = {}
for i in range(M):
    new_list = sorted(list(set(space_list[i])))
    for j in range(len(new_list)):
        dictionary[new_list[j]] = j
    for x in (space_list[i]):
        new_space_list[i].append(dictionary[x])

count = 0
for i in range(M - 1):
    for j in range(i + 1, M):
        if new_space_list[i] == new_space_list[j]:
            count += 1

print(count)

출처: [백준] 18870번 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.

출력

첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 1

1
2

5
2 4 -10 4 -9

예제 출력 1

1

2 3 0 3 1

예제 입력 2

1
2

6
1000 999 1000 999 1000 999

예제 출력 2

1

1 0 1 0 1 0

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 정렬
• 값 / 좌표 압축

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import sys

input = sys.stdin.readline

N = int(input())

coord_list = list(map(int, input().split()))
new_list = sorted(list(set(coord_list)))

d = {}
for i in range(len(new_list)):
    d[new_list[i]] = i

for i in coord_list:
    print(d[i], end=" ")

출처: [백준] 7576번 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 1

1
2
3
4
5

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 1

1

8

예제 입력 2

1
2
3
4
5

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 2

1

-1

예제 입력 3

1
2
3
4
5

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

예제 출력 3

1

6

예제 입력 4

1
2
3
4
5
6

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

예제 출력 4

1

14

예제 입력 5

1
2
3

2 2
1 -1
-1 1

예제 출력 5

1

0

힌트

출처

• Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2013 > 고등부 1번
  • 데이터를 추가한 사람: baekjoon, djm03178
  • 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

시간 제한

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
boxes = [list(map(int, input().split())) for _ in range(M)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs():
    while tomatoes:
        x, y = tomatoes.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < M and 0 <= ny < N and boxes[nx][ny] == 0:
                boxes[nx][ny] = boxes[x][y] + 1
                tomatoes.append((nx, ny))


tomatoes = deque()
for i in range(M):
    for j in range(N):
        if boxes[i][j] == 1:
            tomatoes.append((i, j))

bfs()

alreadyTrue = False
count = 0
for row in boxes:
    for tomato in row:
        if tomato == 0:
            alreadyTrue = True
        count = max(count, tomato)

if alreadyTrue:
    print(-1)
elif count == -1:
    print(0)
else:
    print(count - 1)