졍's 기술 블로그

체스판 다시 칠하기

티어 : Silver 5
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 브루트포스 알고리즘

문제

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

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

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

입력

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

출력

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

예제 입출력

Algorithm

1. 리스트에 string형트로 저장 
2. 보드 잘라내기
    -> 시작좌표 주면 거기서부터 8*8에 해당하는 곳에서 색칠을 다시 해야하는 칸 갯수 반환하는 함수 구현
3. 왼쪽 맨 위가 흰색이라고 가정
  3.1. 이중 for문을 돌면서 흰-검-흰-검-... 순서가 맞는지 확인
  3.2. i 값이 바뀔 때마다 흰색과 검정의 순서 변경
4. 왼쪽 맨 위가 검은색이라고 가정
  4.1. 이중 for문을 돌면서 검-흰-검-흰-... 순서가 맞는지 확인
  4.2. i 값이 바뀔 때마다 흰색과 검정의 순서 변경
5. 2번과 3번 과정 중 최솟값 출력

Code

def count_func(x, y):
    
    if x < 0 or x > N - 8 or y < 0 or y > M - 8:
        return False
    
    now = ['W', 'B']
    count = [0] * 2 # 다시 칠해야 하는 칸의 수를 셀 리스트
    
    # 왼쪽 맨 위가 흰색이라고 가정
    for i in range(x, x + 8):
        for j in range(y, y + 8):
            
            if i % 2 == 0: # 짝수행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 0 # 흰색
                else: # 홀수열이면
                    index = 1 # 검은색
                    
            else: # 홀수 행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 1 # 검은색
                else: # 홀수열이면
                    index = 0 # 흰색
            
            # 원래 있어야 하는 색과 칠해져있는 색이 같지 않으면 count += 1
            if graph[i][j] != now[index]:
                count[0] += 1
    
    # 왼쪽 맨 위가 검은색이라고 가정
    for i in range(x, x + 8):
        for j in range(y, y + 8):
            
            if i % 2 == 0: # 짝수행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 1 # 검은색
                else: # 홀수열이면
                    index = 0 # 흰색
                    
            else: # 홀수 행일 때
                if j % 2 == 0: # 짝수열이면
                    index = 0 # 흰색
                else: # 홀수열이면
                    index = 1 # 검은색
                    
            # 원래 있어야 하는 색과 칠해져있는 색이 같지 않으면 count += 1
            if graph[i][j] != now[index]:
                count[1] += 1
                
    return count

# 입력
N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(input())

min_ = M*N
for i in range(N):
    for j in range(M):

        temp = []
        temp = count_func(i, j)
        
        # 위의 함수를 돌고 나왔을 때 False가 아니라면
        if temp:
            # 최솟값 갱신
            min_ = min(min_, temp[0], temp[1])

print(min_)

메모리: 30864 KB
시간: 124 ms

덩치

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.

티어 : Silver 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 구현, 브루트포스 알고리즘

문제

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

입력

첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다.

출력

여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.

제한

• 2 ≤ N ≤ 50
• 10 ≤ x, y ≤ 200

예제 입출력

Algorithm

1. 리스트에 튜플 형태로 입력
2. 이중 FOR문 돌면서 자신보다 덩치가 큰 사람 수 COUNT해 새로운 리스트에 저장

Code

# 입력
N = int(input())
datas = []
for _ in range(N):
    datas.append(tuple(map(int, input().split())))
    
# 자신보다 덩치가 큰 사람 수 count
count = [0] * N # 덩치 큰 사람의 수를 저장할 리스트
for i in range(N):
    for j in range(N):
        if datas[i][0] < datas[j][0] and datas[i][1] < datas[j][1]:
            # 덩치가 큰 사람이 있으면 count에 추가
            count[i] += 1
            
for i in count:
    print(i+1, end = ' ')

메모리: 30860 KB
시간: 72 ms

오븐 시계

티어 : Bronze 4
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 사칙연산

문제

KOI 전자에서는 건강에 좋고 맛있는 훈제오리구이 요리를 간편하게 만드는 인공지능 오븐을 개발하려고 한다. 인공지능 오븐을 사용하는 방법은 적당한 양의 오리 훈제 재료를 인공지능 오븐에 넣으면 된다. 그러면 인공지능 오븐은 오븐구이가 끝나는 시간을 분 단위로 자동적으로 계산한다.

또한, KOI 전자의 인공지능 오븐 앞면에는 사용자에게 훈제오리구이 요리가 끝나는 시각을 알려 주는 디지털 시계가 있다.

훈제오리구이를 시작하는 시각과 오븐구이를 하는 데 필요한 시간이 분단위로 주어졌을 때, 오븐구이가 끝나는 시각을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 현재 시각이 나온다. 현재 시각은 시 A (0 ≤ A ≤ 23) 와 분 B (0 ≤ B ≤ 59)가 정수로 빈칸을 사이에 두고 순서대로 주어진다. 두 번째 줄에는 요리하는 데 필요한 시간 C (0 ≤ C ≤ 1,000)가 분 단위로 주어진다.

출력

첫째 줄에 종료되는 시각의 시와 분을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수, 분은 0부터 59까지의 정수이다. 디지털 시계는 23시 59분에서 1분이 지나면 0시 0분이 된다.)

예제 입출력

Algorithm

1. 분에 필요한 시간을 더함
2. 분 // 60을 시에 더하고 분 자리에는 분 % 60을 저장
3. 시가 24시를 넘는지 확인

Code

# 입력
A, B = map(int, input().split())
C = int(input())

# 분에 필요한 시간 더함
B += C

# 시와 분 다시 계산
A += (B//60)
B %= 60

# 시가 24시를 넘어가면 0부터 다시 세기
if A > 23:
    A -= 24
print(A, B)

메모리: 30864 KB
시간: 64 ms

주사위 세개

티어 : Bronze 4
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 사칙연산

문제

1에서부터 6까지의 눈을 가진 3개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다.

1. 같은 눈이 3개가 나오면 10,000원+(같은 눈)×1,000원의 상금을 받게 된다. 
2. 같은 눈이 2개만 나오는 경우에는 1,000원+(같은 눈)×100원의 상금을 받게 된다. 
3. 모두 다른 눈이 나오는 경우에는 (그 중 가장 큰 눈)×100원의 상금을 받게 된다.  

예를 들어, 3개의 눈 3, 3, 6이 주어지면 상금은 1,000+3×100으로 계산되어 1,300원을 받게 된다. 또 3개의 눈이 2, 2, 2로 주어지면 10,000+2×1,000 으로 계산되어 12,000원을 받게 된다. 3개의 눈이 6, 2, 5로 주어지면 그중 가장 큰 값이 6이므로 6×100으로 계산되어 600원을 상금으로 받게 된다.

3개 주사위의 나온 눈이 주어질 때, 상금을 계산하는 프로그램을 작성 하시오.

입력

첫째 줄에 3개의 눈이 빈칸을 사이에 두고 각각 주어진다.

출력

첫째 줄에 게임의 상금을 출력 한다.

예제 입출력

Algorithm

1. 입력 값을 Dictionary에 추가 (개수 count)
2. for문을 돌면서 value가 3이면 10000 + key * 100
3. value가 2이면 1000 + key * 100
4. 그 외의 상황이면 max(key) * 100

Code

# 입력
data = list(map(int, input().split()))

# 입력 값 Dictionary에 저장 (key: 입력 값, value: 횟수)
dict_ = {}
for i in data:
    if i not in dict_:
        dict_[i] = 1
    else:
        dict_[i] += 1

flag = False # 같은 숫자가 있는 경우 False, 모두 다른 경우 True
for key, value in dict_.items():
    if value == 3:
        print(10000 + key * 1000)
        flag = False
        break
    elif value == 2:
        print(1000 + key * 100)
        flag = False
        break
    else:
        flag = True

if flag:
    print(max(dict_.keys()) * 100)

메모리: 30864 KB
시간: 68 ms