졍's 기술 블로그

날짜 계산

티어 : Silver 5
시간 제한 : 2 초
메모리 제한 : 4 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론, 중국인의 나머지 정리

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입출력

Algorithm

1. 현재 시간 1 증가
2. e, s, m 1 증가
    ☞ 각각 15, 28, 19를 넘으면 1로 초기화

Code

E, S, M = map(int, input().split())

e, s, m = 0, 0, 0
time = 0
while True:
    time += 1
    
    if e == 15:
        e = 1
    else:
        e += 1
        
    if s == 28:
        s = 1
    else:
        s += 1
        
    if m == 19:
        m = 1
    else:
        m += 1
        
    if e == E and s == S and m == M:
        break

print(time)

메모리: 30860 KB
시간: 72 ms

사탕 게임

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

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입출력

힌트

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

Algorithm

1. 사탕의 색상을 2차원 리스트 board에 저장
2. board를 하나씩 확인하면서 행에 같은 사탕이 몇 개인지 세기
2.1. 행: board[i][j]부터 board[i][j+1]까지 같은 색이면 count + 1
                                                    다른 색이면 count 1로 초기화하고 continue
2.2. 열: board[i][j]부터 board[i+1][j]까지 같은 색이면 count + 1
                                                    다른 색이면 count 1로 초기화하고 continue
3. board를 하나씩 확인하면서 열에 같은 사탕이 몇 개인지 세기
3.1. 행: board[i][j]부터 board[i][j+1]까지 같은 색이면 count + 1
                                                    다른 색이면 count 1로 초기화하고 continue
3.2. 열: board[i][j]부터 board[i+1][j]까지 같은 색이면 count + 1
                                                    다른 색이면 count 1로 초기화하고 continue

Code

import sys
input = sys.stdin.readline

N = int(input())
board = []
for _ in range(N):
    board.append(list(input().rstrip()))

# 행을 기준으로 다른 색상 교환
max_count = 1
for i in range(N):
    for j in range(N-1):
        # 인접한 행의 색상이 다르면 교환
        if board[i][j] != board[i][j+1]:
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
            
            # 교환했을 때 사탕의 최대 개수 체크
            
            # 행 확인
            for x in range(N):
                count = 1
                for y in range(N-1):
                    # 인접한 행의 색상이 같으면 count 증가
                    if board[x][y] == board[x][y+1]:
                        count += 1
                        
                    else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
                        if max_count < count:
                            max_count = count
                        count = 1
                        continue
                    
                    if max_count < count:
                        max_count = count
                        
            # 열 확인
            for y in range(N):
                count = 1
                for x in range(N-1):
                    # 인접한 열의 색상이 같으면 count 증가
                    if board[x][y] == board[x+1][y]:
                        count += 1
                        
                    else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
                        if max_count < count:
                            max_count = count
                        count = 1
                        continue
                    
                    if max_count < count:
                        max_count = count
                    
            # 교환했던 칸 원위치
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

# 열을 기준으로 다른 색상 교환
for j in range(N):
    for i in range(N-1):
    
        # 인접한 열의 색상이 다르면 교환
        if board[i][j] != board[i+1][j]:
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

            # 교환했을 때 사탕의 최대 개수 체크
            # 행 확인
            for x in range(N):
                count = 1
                for y in range(N-1):
                    # 인접한 행의 색상이 같으면 count 증가
                    if board[x][y] == board[x][y+1]:
                        count += 1
                        
                    else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
                        if max_count < count:
                            max_count = count
                        count = 1
                        continue
                    
                    if max_count < count:
                        max_count = count
            
            # 열 확인
            for y in range(N):
                count = 1
                for x in range(N-1):
                    # 인접한 열의 색상이 같으면 count 증가
                    if board[x][y] == board[x+1][y]:
                        count += 1
                    else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
                        if max_count < count:
                            max_count = count
                        count = 1
                        continue
                    
                    if max_count < count:
                        max_count = count
                    
            # 교환했던 칸 원위치
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

print(max_count)

메모리: 30864 KB
시간: 4296 ms

일곱 난쟁이

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

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

예제 입출력

Algorithm

완전 탐색 이용
1. 난쟁이의 키를 리스트로 입력
2. 두 개씩 뺀 후 리스트의 합이 100이 되는지 확인

Code

import sys
input = sys.stdin.readline

heights = [0 for _ in range(9)]
for i in range(9):
    heights[i] = int(input())

# 리스트 오름차순
heights.sort()

# 리스트에서 두개씩 빼어 리스트의 합이 100이 되는지 확인
temp = []
for i in range(len(heights)):
    for j in range(i, len(heights)):
        if sum(heights[:i]+heights[i+1:j]+heights[j+1:]) == 100:
            temp += heights[:i] + heights[i+1:j] + heights[j+1:]
            break
    if len(temp) > 0:
        break
    
answer = ''
for i in temp:
    answer += str(i) + '\n'
print(answer)

메모리: 30860 KB
시간: 68 ms

골드바흐의 추측

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 정수론, 소수 판정, 에라토스테네스의 체

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

예제 입출력

Algorithm

1. 아레토스테네스의 체를 이용해 입력된 값 중 MAX값을 기준으로 소수 리스트 생성
2. 입력받은 값보다 작은 홀수인 소수로 해당 값을 만들 수 있는지 확인

Code

import sys
import math
input = sys.stdin.readline

nums = []
while True:
    num = int(input())
    if num == 0:
        break
    nums.append(num)

# 에라토스테네스의 체를 이용해 MAX(입력값)를 기준으로 소수 리스트 생성
MAX = max(nums)
prime = {}
for i in range(MAX+1):
    prime[i] = True
prime[1] = False
for i in range(2, int(math.sqrt(MAX + 1))):
    if prime[i]:
        for j in range(i*2, MAX, i):
            prime[j] = False

# 입력받은 수보다 작은 홀수 소수로 해당 값을 만들 수 있는지 확인
answer = ''
for i in nums:
    for j in range(i-3, 0, -2):
        if prime[j] and prime[i - j]:
            answer += str(i) + ' = ' + str(i-j) + ' + ' + str(j) + '\n'
            break
    if j == 1:
        answer += 'Goldbach\'s conjecture is wrong.\n'
print(answer)

메모리: 118412 KB
시간: 704 ms

소수 구하기

티어 : Silver 3
시간 제한 : 2 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 정수론,소수 판정, 에라토스테네스의 체

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입출력

Algorithm

1. 1부터 N까지 숫자 리스트 생성
2. 2부터 루트 N까지의 숫자로 리스트 내의 숫자를 순차적으로 나누면서 나누어떨어지는 수 Fasle 표시
3. M부터 N까지의 숫자 중 True 값 갖는 숫자만 출력

Code

import math

# 입력
M, N = map(int, input().split())
# 1부터 N까지 숫자 리스트 생성
nums = [True for _ in range(N+1)]
nums[1] = False # 1은 소수가 아니므로 False 저장

# 2부터 루트 N + 1까지의 숫자로 나눔
for i in range(2, int(math.sqrt(N) + 1)):
    # 현재 숫자가 나누어진 적 없다면
    if nums[i]:
        # i * 2부터 N을 넘지 않을 때까지의 숫자를 모두 Fasle로 저장
        j = 2
        while i*j < N+1:
            nums[i*j] = False
            j += 1

answer = ''
for i in range(M, N+1):
    if nums[i]:
        answer += str(i) + '\n'
print(answer)

메모리: 42080 KB
시간: 684 ms

약수의 합 2

티어 : Silver 2
시간 제한 : 0.5 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 수학, 정수론

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

예제 입출력

Algorithm

N까지의 약수 중 i라는 숫자는 N//i개 존재
-> i가 1부터 N까지 증가하면서 i의 개수 * i 더하기

Code

N = int(input())
sum_ = 0
for i in range(1, N+1):
    sum_ += i * (N//i)
print(sum_)

메모리: 30864 KB
시간: 240 ms

요세푸스 문제

티어 : Silver 4
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 구현, 자료 구조, 큐

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입출력

Algorithm

Queue 구현 - deque library 사용
1. queue에 1부터 N까지 숫자로 채움
2. append(queue[0]), popleft()를 두 번 수행
3. print(queue[0]), popleft() 수행
4. queue가 빌 때까지 반복

Code

from collections import deque
N, K = map(int, input().split())
queue = deque([i for i in range(1, N+1)])
answer = []
while queue:
    # append, popleft 두 번 수행
    for _ in range(K - 1):
        queue.append(queue[0])
        queue.popleft()

    # print, popleft 수행
    answer.append(queue[0])
    queue.popleft()

print('<', end = '')
for i in range(len(answer)):
    if i == len(answer) - 1:
        print(answer[i], end = '>')
    else:
        print(answer[i], end = ', ')

메모리: 32360 KB
시간: 144 ms

카드2

티어 : Silver 2
시간 제한 : 2 초 (추가 시간 없음)
메모리 제한 : 128 MB
알고리즘 분류 : 자료 구조, 큐

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입출력

Algorithm

Queue 구현 - deque library 사용
1. queue에 1부터 n까지 숫자로 채움
2. popleft()로 맨 위의 카드 버림
3. append(queue[0])로 맨 위의 카드 맨 마지막으로 보내기
4. popleft()로 맨 위의 카드 버림
5. 카드가 한 장 남을 때까지 반복

Code

from collections import deque

N = int(input())
queue = deque([i for i in range(1, N+1)])

while len(queue) > 1:
    # 맨 위의 카드 버리기
    queue.popleft()
    
    # 그 다음 맨 위의 카드 버리고 캔 아래 카드 아래로 보내기
    queue.append(queue[0])
    queue.popleft()

print(queue[0])

메모리: 53324 KB
시간: 260 ms