[1463] 1로 만들기

일단 처음에 재귀라고 생각을 했는데 실행시간이 짧아서 DP라고 생각은 들었는데 어떻게 해결해나갈지 감이 잘 안왔다.

DP부분이 약해서 그냥 제미나이한테 도움을 받았다. (그런데 틀림)

 

틀린 코드

import sys

input = sys.stdin.readline

n = int(input())

d = [0] * (n+1)

for i in range(2, n+1):

    d[i] = d[i-1] + 1

    if i%2 == 0:

        d[i] = min(d[i], d[i//2] + 1)

    elif i%3 == 0:

        d[i] = min(d[i], d[i//3] + 1)

print(d[n])

 

DP 초기 부분이 틀리지 않았을까 생각했다. 

 

가변적으로 설정하니까 d[2]=1 값을 지정이 불가능해서 값을 최댓값 리스트까지 초기화 시켜보았다.

 

틀린 코드

import sys

input = sys.stdin.readline

n = int(input())

d = [0] * 10000000

d[1] = 1

d[2] = 1

d[3] = 1

for i in range(4, n+1):

    d[i] = d[i-1] + 1

    if i%2 == 0:

        d[i] = min(d[i], d[i//2] + 1)

    elif i%3 == 0:

        d[i] = min(d[i], d[i//3] + 1)

print(d[n])

 

 

3으로 나눌 경우를 elif로 해버려서 실수했다.

그리고 1인 경우 (d[1])은 당연히 목적값이니 0회인데 1로 설정해버렸다.

 

정답 코드

import sys

input = sys.stdin.readline

n = int(input())

d = [0] * 10000000

d[1] = 0

d[2] = 1

d[3] = 1

for i in range(4, n+1):

    d[i] = d[i-1] + 1

    if i%2 == 0:

        d[i] = min(d[i], d[i//2] + 1)

    if i%3 == 0:

        d[i] = min(d[i], d[i//3] + 1)

print(d[n])