[DP] 백준 1로 만들기 1463번 with Python3

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

문제

내 풀이

import sys
n = int(input())
a = sys.maxsize
dp_table = [[a] * ((n//2)+1) for _ in range(n+1)]
# dp_table[num][step]
dp_table[n][0] = 1

# for i in dp_table:
#     print(i)

for step in range(1, ((n//2)+1)):
    for num in range(1, n):
        j = n - num
        if j*3 <= n:
            A = dp_table[j*3][step-1]
        else:
            A = float('inf')
        if j*2 <= n:
            B = dp_table[j*2][step-1]
        else:
            B = float('inf')
        dp_table[j][step] = min(dp_table[j+1][step-1], A, B) + 1

# for i in dp_table:
#     print(i)

print(min(dp_table[1])-1)

해설

나름 dp를 이용해 풀어보려 했으나, 메모리 초과, 시간 초과, 그냥 무지성 bfs 탐색이 더욱 효율적이었을거 같다.

 

정답 풀이

n = int(input())
d = [0] * (n + 1)	## d에 계산된 값을 저장해둔다. n + 1이라고 한 이유는, 1번째 수는 사실 d[1]이 아니고 d[2]이기 때문에, 계산하기 편하게 d[1]을 1번째 인 것 처럼 만들어준다.

for i in range(2, n + 1):
## 여기서 왜 if 1빼는 방법, 2 나누기, 3 나누기 동등하게 하지 않고 처음에 1을 빼고 시작하는지 의아해 할 수 있다.
## 1을 빼고 시작하는 이유는 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문이다.
## 즉 셋 다 시도하는 방법이 맞다.

    d[i] = d[i - 1] + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)	## 1을 더하는 것은 d는 결과가 아닌 계산한 횟수를 저장하는 것 이기 때문이다. d[i]에는 더하지 않는 이유는 이미 1을 뺄 때 1을 더해준 이력이 있기 때문이다.
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
print(d[n])

출처:https://jae04099.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-1463-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0

 

해석

너무 직관적으로 좋다. dp라는 것은 이렇게 써야 할텐데. 후.

상향식으로 1부터 출발해서 n에 도달하는 최단거리를 출력하는 식이다.