[백준] 12852번: 1로 만들기2

문제

백준 12852번

<문제 정리>

정수 X에 사용할 수 있는 연산
1. X%3 == 0, 3으로 나누기
2. X%2 == 0, 2로 나누기
3. 1 빼기
정수 N이 주어졌을 때 연산 세 개 활용 해 1 만들기
연산을 사용하는 횟수의 최솟값

입력: 1<N<10**6
출력: 첫째 줄에 연산을 하는 횟수의 최솟값
둘째 줄에 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해 순서대로 출력
정답이 여러가지인 경우 아무거나 출력

내가 좋아하는 동적계획법 문제다.

설명

동적계획법을 좋아하는 이유는 점화식만 잘 짜면 코드가 술술 나오기 때문인데,
나는 다음과 같은 순서대로 점화식을 짠다.

N: 입력값이고,

만들 것은 다음과 같다.
1) 연산 횟수를 업데이트하는 리스트
2) resultList = 1~N까지 연산 결과 전부를 업데이트하는 리스트

<resultList를 따로 만든 이유>
핵심은 두번째 출력 조건때문인데,
1로 만들기1 문제에서는 횟수의 최솟값만 출력하면 됐다.

그런데 1과 달리 2에서는 지금껏 계산한 결과들이 필요하기 때문에 그때그때 연산한 결과를 넣어주는 리스트가 필요한 것이다.

• T[N] 연산 횟수
• T[2] = 1, resultList = [0, 0, 1]
• T[3] = 1, resultList = [0, 0, 1, 1]
• T[4] = 2, resultList = [0, 0, 1, 1, 2]

T[N] 메모이제이션 시작하는데, 기본적으로 <-1 연산>한 것을 저장한다.
=> T[N] = T[N-1] + 1

그 다음에 조건문을 돌리는데,
N%2 == 0 의 경우 <//2 연산>
=> T[N-1] + 1 > T[N//2]+1을 만족하면, 최솟값으로 바꿔치기
=> T[N] = T[N//2]+1
=> resultList[N]도 결과값으로 바꿔치기
N%3 == 0 의 경우 <//3 연산>
=> T[N-1] + 1 또는 T[N//2]+1 > T[N//3]+1을 만족하면, 최솟값으로 바꿔치기
=> T[N] = T[N//3]+1
=> resultList[N]도 결과값으로 바꿔치기

코드

def makeOpList(num):
    opList = [None for _ in range(num+1)]
    resultList = [0 for _ in range(num+1)]
    opList[1] = 0

    for i in range(2, num+1):
        opList[i] = opList[i-1] + 1
        resultList[i] = i - 1
        if i%2 == 0:
            if opList[i]>opList[i//2]+1:
                opList[i] = opList[i//2]+1
                resultList[i] = i//2
        if i%3 == 0:
            if opList[i]> opList[i//3]+1:
                opList[i] = min(opList[i], opList[i//3]+1)
                resultList[i] = i//3
    return opList[num], resultList
    
num = int(input())

answer01, answer02 = makeOpList(num)
print(answer01)

while True:
    print(num, end=" ")
    num = answer02[num]
    if num==0: break

메모이제이션 시 전체 범위의 for문을 돌릴 수 밖에 없고,
따라서 연산 결과 전부를 업데이트해야한다.

그래서 resultList를 출력할 때 index로 결과값을 접근하여 바로 출력하는 방식을 택했다.

출력된 값을 resultList의 index로 가지는 값이 그 다음에 출력되도록 생성

ex. N = 10
resultList = [0, 0, 1, 1, 3, 4, 3, 6, 4, 3, 9] 10(입력값)

출력 순서        ([5])   [4]               [3][2][1] 

1. 10(출력) -> resultList[10]
2. resultList[10] = 9(출력) -> resultList[9]
3. resultList[9] = 3(출력) -> resultList[3]
4. resultList[3] = 1(출력) -> resultList[1]
5. resultList[1] = 0(끝)