📌문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
예제
예제 입력1
2예제 출력1
1예제 입력2
10예제 출력2
3💡Idea
동적계획법(dynamic programming)을 사용하면 해결할 수 있는 문제입니다.
동적계획법은 복잡하고 큰 문제를 작고 간단한 여러 개의 문제로 나누어 푸는 방식으로, 작은 문제들의 결과들을 모두 저장해두고 큰 문제를 해결할 때 사용합니다.
사실 처음에는 입력과 출력 사이의 규칙을 찾아 조건을 걸어 문제를 해결하려고 했습니다. 그런데, 아무리 규칙을 찾고 조건을 걸어도 예외가 존재했고, 그 예외들을 계속해서 처리하다보니 코드가 아주 지저분해졌어요😂
👇 해결하려고 애썼던 요지경 코드
import sys
N = int(sys.stdin.readline())
answer = 0
while N != 1:
if N % 3 == 0:
N = N / 3
# 아래와 같이 예외들을 처리하려다 보니 조건이 계속해서 늘어납니다
elif (N % 2 == 0 and N % 3 > 1) or (N % 4 == 0 and (N - 1) % 3):
N = N / 2
else:
N = N - 1
answer += 1
print(answer)
그러다가 큰 수들은 그 아래의 작은 수들의 결과를 사용한다는 것을 알게 되었습니다.
예를 들어, 11은 3번으로 만들 수 있는 10에 1을 더한(1을 빼는 연산) 4가 정답이 되는 것처럼요!
그래서 이런 동적 계획법으로 문제를 해결하였습니다.
💻코드1
import sys
N = int(sys.stdin.readline())
dp = [0 for i in range(N + 1)]
for i in range(2, N+1): #1
dp[i] = dp[i - 1] + 1 #2
if i % 3 == 0: #3
dp[i] = min(dp[i], dp[i // 3] + 1)
if i % 2 == 0: #4
dp[i] = min(dp[i], dp[i // 2] + 1)
print(dp[N])📝코드 설명
변수
N: 주어진 정수dp: 각 정수 별 연산을 하는 횟수를 담은 리스트
#1 : 1인 경우에는 연산을 하지 않아도 되기 때문에 제외하고, 2부터 우리가 구해야 하는 N까지 연산을 해야 하는 횟수를 구합니다.
#2 : i에서 1을 빼는 연산을 하면 i-1가 되기 때문에 i-1의 연산 횟수에서 1을 더한 만큼의 연산을 하면 i의 연산 횟수를 구할 수 있습니다.
#3 : i가 3으로 나누어떨어지는 수인 경우, 현재 dp[i]와 dp[ i // 3] + 1(+1은 3으로 나누는 연산을 더한 것) 중 작은 값을 선택합니다.
4 : i가 2으로 나누어떨어지는 수인 경우, 현재 dp[i]와 dp[ i // 2] + 1(+1은 2으로 나누는 연산을 더한 것) 중 작은 값을 선택합니다.
💻코드2
import sys
N = int(sys.stdin.readline())
dic = {1: 0, 2: 1}
def dp(n):
if i in dic: # 이미 최소 연산 횟수를 계산한 값이라면 dic에서 찾아 return
return dic[i]
cnt = 1 + min(dp(i // 3) + i % 3, dp(i // 2) + i % 2) #1
dic[i] = cnt
return cnt
print(dp(N))📝코드 설명2
코드 1과는 다르게 재귀적인 방식으로도 문제를 해결할 수 있습니다.
코드 1은 2부터 N까지의 모든 값들의 연산 횟수를 계산하지만 코드2는 필요한 값들만을 계산하기 때문에 코드1에 비해서 훨씬 빠릅니다.
변수
N: 주어진 정수dp: 각 정수 별 연산을 하는 횟수를 담은 딕셔너리로, key는 정수, value는 연산의 횟수
#1 : 3이나 2로 나누어지지 않으면 무조건 둘 중 하나로 나누어질 수 있도록 1을 빼주는 연산을 해야 합니다. 따라서 i를 3 혹은 2로 나눈 나머지만큼 1을 빼주어야 하므로 나머지 값을 더해주는 것입니다.
그리고 3과 2로 나누어서 진행하는 값 중 작은 값을 선택해줍니다.
Reference
