1로 만들기

1. 정답 코드

문제의 정답 코드는 다음과 같다.

x = int(input())
d=[0]*(x+1)

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

    #무조건 1을 빼는 경우가 있으니까
    d[i] = d[i-1] + 1

    #그리고 2,3,5로 나눠지는 경우를 다 따져보자.
    #이때 2,3,5 순으로 하는 것이 포인트다. 왜냐하면 작은수로 나눌수록 경우가 더 많아지기 때문이라 생각
    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)
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

for j in range(1,len(d)):
    print("f({0})의 경우의 수는 {1} 이다.".format(j,d[j]))

print("결국 f({0})의 최단 경우의 수는 {1}이다.".format(x,d[x]))

다이나믹 프로그래밍 문제의 가장 기본 예시라고 한다. 피보나치 수열을 재귀형식(탑다운)으로 푸는 것을 배웠지만, 사실 DP는 탑다운보다 반복문의 바텀업 형식으로 푸는 것이 더 좋다고 한다. 그래서 그 형식도 배우고 위 문제를 처음 접했는데, 처음 공부하다보니 굉장히 난해했다.. 이해가 하나도 안갔지만, 이거 포기하면 개발자로써 한발을 나설 수 있겠는가! 끈질기게 파헤쳐서 얻은 나만의 생각을 기록하고자 한다.

2. 문제 풀이

일단 바텀업 방식을 위해 DP 테이블을 초기화 해야한다.

d=[0]*(x+1)

그리고 바로 반복문을 들어가자.

이 문제는 숫자 x를 입력받으면, 2,3,5로 나누거나 -1을 해서 x를 1로 만드는 최소의 횟수를 물어본다. 사실 어떤 숫자든 -1을 하는 것은 x가 1이 아닌 이상 항상 가능하다. 그래서 아래 코드를 통해 그 경우의 수를 항상 먼저 새겨넣는다.

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

그리고 2,3,5 순으로 값을 나눠봐야한다.

    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)
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

이때 elif을 쓰면 안된다. 모든 경우의 엣지 연결을 만들어내야하기 때문에, 2,3,5로 나눠지는 경우를 다 구해봐야 하는 것이다. 그리고 작은거부터 나눠보는 이유는 작은 거로 나눌 수록 경우의 수가 더 늘어날 것이라고 생각된다.

각각 나눠보고 딱 나눠떨어지면 이제 비교를 해야한다. 이때 비교라는 것은 -1만 한 것과 비교해보는 거다. 이전 노드 d[i-1]에서 1을 더한 것(현재 d[i])와 나눈 것의 노드에 1을 더한 것(d[i//n]+1)의 경우의 수를 비교하는 것이다. 여기서 1을 더하는 이유는 나눈 횟수를 +1 해주는 것이다. 비교해서 더 작은 것을 현재 d[i]로 재설정한다. 이렇게 계속해서 제일 작은 것들로 갱신해주면서 우리가 원하는 최소의 경우의 수 d[x]를 구할 때까지 for문이 돌아가는 것이 핵심.