[ProblemSolving] 백준 - 12852 1로만들기2(dp)

문제 링크

문제 설명

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
   정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력1

2

예제 출력1

1
2 1

예제 입력2

10

예제 출력2

3
10 9 3 1

나의 풀이

dp의 보텀업(for문) 방식으로 해결했다!

왜 dp일까?
이처럼 f(2), f(3) 같은 함수가 여러번 호출되고, 같은 함수는 값이 다 동일하기 때문에 dp테이블에 저장해서 필요할 때 사용하는 것이 효율적이다.

호출 횟수에 대한 점화식은 dp[i] = min(dp[i-1], dp[i//2], dp[i//3] ) +1 이다.

뒤에 +1은 호출 횟수를 구해야 하기 때문에 필요하다.

여기까지는 1로만들기_1463과 같다.

1로만들기 코드 참고

n = int(input())
dp= [0]*(n+1) 
# 보텀업으로 해결, 뒤에 더하기 1은 카운트
for i in range(2, n+1):
    dp[i] = dp[i-1]+1
    if i % 2 ==0:
        dp[i] = min(dp[i], dp[i//2] +1)
    if i % 3 ==0:
        dp[i] = min(dp[i], dp[i//3] +1)     
    if i % 5 ==0:
        dp[i] = min(dp[i], dp[i//5] +1)
    
print(dp[n])  

이 문제에서는 경로도 출력해줘야 하므로, if dp[i][0] > dp[i//2][0]+1 식으로 갱신 조건을 주어서 만족하면, dp[i][1] = i//2 연산한 값을 저장한다.

temp 리스트를 생성하여, 호출 횟수만큼 저장된 연산값을 담아서
문자열로 출력해준다.

코드

n = int(input())
dp = list([0,0] for _ in range(n+1)) 

for i in range(2, n+1):
    dp[i][0] = dp[i-1][0]+1
    dp[i][1] = i-1

    if i % 2 ==0:
        if dp[i][0] > dp[i//2][0]+1: # 갱신조건을 준다.
            dp[i][0] = dp[i//2][0]+1
            dp[i][1] = i//2
        
    if i % 3 ==0:
        if dp[i][0] > dp[i//3][0]+1:
            dp[i][0] = dp[i//3][0]+1
            dp[i][1] = i//3
    
print(dp[n][0])

temp = []
temp.append(n)
for _ in range(dp[n][0], 0, -1):
    temp.append(dp[n][1])
    n = dp[n][1]
    
print(' '.join(map(str, temp)))