[Python] 백준 1463 1로만들기

코드 작성

n = int(input())
d = [0] * (n + 1)
for i in range(2, n + 1):
    d[i] = d[i - 1] + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)	
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
print(d[n])

 

문제 풀이

다이나믹 프레그래밍은 전에 했던 루트를 다시 반복하고 새로운 명령어에 한가지 방법을 추가한다.

숫자 10은 3으로 나누어 떨어지지 않기 때문에

10 > 5 > 4 > 2 > 1 순서로(4번) 생각해 볼 수 있지만,

10 > 9 > 3 > 1의 순서로(3번) 나타낼 수 있다.

 

마찬가지로 9의 값은

9 > 3 > 1로 표현(2번)되며

3의 값은

3 > 1로 표현(1번)된다.

즉, 10의 값은 전에 했던 루트에 한 가지만 추가하여 생성된 값이다.

 

코드 이해(예시)

d[2]의 경우 d[1]의 경우에 1을 추가한 값이다.

d[3]의 경우 d[2]의 경우에 1을 추가한 값이다.

d[4]의 경우 d[2]의 경우에 2를 곱한 값이다.

d[5]의 경우 d[4]의 경우에 1을 더한 값이다.

d[6]의 경우 d[2]의 경우에 3을 곱한 값이다.

d[7]의 경우 d[6]의 경우에 1을 더한 값이다.

d[8]의 경우 d[4]의 경우에 2를 곱한 값이다.

 

이해를 돕기 위한 틀린 코드 

n = int(input())
d = [0] * (n + 1)
for i in range(2, n + 1):
    c1 = d[i-1]+1    #Case1
    c2 = d[i//2]+1   #Case2
    c3 = d[i//3]+1   #Case3
    d[i]=min(c1,c2,c3)
print(d[n])

위 코드 식에서

c1은 1을 더한 값

c2는 2를 곱한 값

c3는 3을 곱한 값

으로 정하여 c1, c2, c3중 최솟값을 d[i]라고 하여 출력하면 된다.

 

다만, i가 2로 나누어 떨어지지 않는 경우 소수점을 버림하기 때문에 5//2는 2값을 출력해서 틀린다. 또한, c1,c2,c3의 값이 for문 i의 조건마다 계속해서 숫자가 초기화되지 않는다. 따라서 젤 위에 작성한 것과 같은 코드식이 나온다.