Problem
https://www.acmicpc.net/problem/1463
Solution
오답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
x = int(input())
n = 0
while True:
if x == 1 : break
elif x % 3 == 0 :
x = x/3
n = n+1
if x == 1 : break
else : continue
elif x % 2 == 0 :
x = x/2
n = n+1
if x == 1 : break
else : continue
else :
x = x-1
n = n+1
if x == 1 : break
else : continue
print(n)
문제에 제시된 연산 세가지에 순서가 부여됐다고 착각해서 코드를 틀리게 작성했다. 힌트의 10을 입력했을 때 출력값이 다르게 나왔다. 내 코드를 적용했을 때는 10→5→4→2→1 로 4가 나오지만 힌트에서는 10→9→3→1로 3이 나오게 된다. 구글링을 해보니 이런 다이나믹 프로그래밍은 점화식을 활용해야 문제를 해결할 수 있다고 한다.
정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
def make_one(n):
arr = [0, 0, 1, 1] # 1로 만드는 최솟값 저장(3까지)
for i in range(4, n+1):
one, two, three = n, n, arr[i-1] # one, two가 결과값을 방해하지 않도록 n으로
if i % 3 == 0:
one = arr[i//3]
if i % 2 == 0:
two = arr[i//2]
arr.append(1 + min(one, two, three)) # (3가지 방법 중 최솟값+1)로 저장
return arr[n]
n = int(input())
print(make_one(n))
DP 중 Bottom-up 방식을 사용하여 해결한 코드이다.