1로 만들기 - 1463

문제링크

문제 링크

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

풀이

• DP[N]의 값은 N으로 1을 만드는 최소 횟수임
• DP[N]의 처음 1, 2값(0, 1)을 알고 있으므로, 상향식으로 풀 것임
• N이 3으로 나누어 떨어지면, DP[N] = DP[N//3]+1
• N이 2로 나누어 떨어지면, DP[N] = DP[N//2] + 1
• 나머지는, DP[N] = DP[N-1] + 1
• 위의 세 가지 중 최솟 값을 구함

코드

from sys import stdin

n = int(stdin.readline())

# dp배열의 인덱스 값에 해당하는 숫자의 1을 만드는 최솟 값을 저장
# 사용하기 쉽도록 n+1 사이즈의 배열로 만들어 index 1의 값은 0, index 2의 값은 1 저장

dp = [0 for _ in range(n+1)]

# 처음 두 값은  우리가 아니깐 상향식으로
dp[1] = 0
dp[2] = 1

# 세 가지 경우 다 비교할거임
# 3번,2번 이랑 비교하고, 2번, 1번이랑 비교하고
for i in range(3, n+1):

    dp[i] = dp[i-1] + 1 #3번, x-=1에 해당
    if i % 2 == 0 :
        dp[i] = min(dp[i], dp[i//2]+1) #3번, 2번 비교
    if i % 3 == 0 :
        dp[i] = min(dp[i], dp[i//3]+1) #2번, 1번 비교

print(dp[n])

느낀점

다이나믹 프로그래밍은 처음인데, 여러 기발한 방법을 시도 했지만 위 코드와 같은 프로그래밍은 하지 못했고… 결국 다른 사람의 해답을 배꼇지만 이해하는 시간도 꽤 적게 걸리지 않았다. 나만의 방법을 만들고, 또 많은 문제를 풀어야 겠음