[Baekjoon 1463 / python / 실버3] 1로 만들기

x = int(input())

d = [0] * ((10 ** 6) + 1)

for i in range(2, x + 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[x])

 

다이나믹 프로그래밍 문제이다.

d는 메모이제이션(값을 저장해 놓을)할 리스트.

i는 현재 계산중인 숫자

d[i] 는 i에 대한 최소연산횟수이다.

숫자 2부터 바텀 업 방식으로 d리스트를 채워나가 최종적으로 x의 최소연산횟수를 구하는 것이다.

 

이 문제는 3가지 연산을 할 수 있다.

1을 빼기, 2로 나누기, 3으로 나누기

하지만 2나 3으로 나눠진다고 해서 무조건 나누면 안 되고, 무조건 3개 연산을 다 해본 후 연산횟수가 가장 적은 걸 선택해야 한다.

 

2에 대한 최소연산횟수, 3에 대한 최소연산횟수..... 쭉쭉 올라가 x에 대한 최소연산횟수까지 도출되게 된다.

+1을 왜 하는지 헷갈릴 수 있는데, i // 3을 하여 숫자를 한번 줄이는 건 연산을 1번 한 것이기 때문에 d[i]에 연산횟수 + 1을 해 주는 것이다.