1로 만들기 2

문제 분석

‘1로 만들기 - 1463번’에 1로 만드는 과정을 출력하는 것이 더해진 문제이다.

먼저, ‘1로 만들기 - 1463번’에 대해 생각해보자.

10처럼 2로 나누어 떨어지더라도, 2로 바로 나누지 않고 1을 먼저 빼준 후에 3으로 두번 나눠주는 것이 더 짧게 1로 만들 수 있는 방법이다. 이처럼 2랑 3으로 나누어주는 것이 항상 유리하지 않음으로 DP를 이용해 숫자들에 대해 탐색해 나가야 한다.

• 임의의 숫자 i에 대해서, 우선 dp[i]에 dp[i-1]+1의 값을 넣어준다.
• 만약 i가 2의 배수라면, dp[i]에 max(dp[i],dp[i//2]+1)을 넣는다.
• i가 3의 배수일 때도, 위의 과정을 동일하게 반복해준다.

이 과정을 우리가 원하는 숫자 n 까지 반복해주면 된다.

CODE - 1463번

n=int(input())
dp=[-1 for _ in range(n+1)]
dp[1]=0
for i in range(1,n+1):
    if dp[i]== -1:
        dp[i]=dp[i-1]+1
        if i%3==0:
            if dp[i]>dp[i//3]+1:
                dp[i]=dp[i//3]+1
        if i%2==0:
            if dp[i]>dp[i//2]+1:
                dp[i]=dp[i//2]+1
print(dp[n])

1로 만들기 2 문제는 여기에, 1로 만드는데 거친 숫자들까지 출력해주면 된다. 과정으로 거쳐온 숫자들을 DP에 추가로 저장하기 위해 길이가 2인 리스트를 원소로 가지는 DP를 생성했다.

위의 그림과 같이 각각의 DP원소에 해당 숫자를 1로 만드는데 요구되는 최소 연산 횟수와 최소 연산 횟수를 가지기 위해 거쳐온 직전의 숫자를 저장했다.

10의 경우를 예로 들어보자.

• 10은 2로 나누어 떨어짐으로, DP[5]와 DP[9]를 비교한다.
• DP[9]의 연산횟수가 더 작음으로, DP[10]의 연산횟수는 DP[9]의 연산횟수 +1 그리고 DP[10]의 직전숫자는 9가 되게 된다.
• 이 과정을 반복하면, 10 > 9 > 3 > 1의 과정을 통해 1로 변하게 됨을 확인할 수 있고, 그 경로는 DP에 저장되게 된다.
• DP의 직전 숫자들을 따라가면 그 숫자들이 곧 해당 숫자를 1로 만드는 과정인 셈이다.

CODE

import sys
read=sys.stdin.readline
n=int(read())

dp=list([-1,-1] for _ in range(n+1))
dp[1]=[0,0]
for i in range(2,n+1):
    dp[i]=[dp[i-1][0]+1,i-1]
    if i%2==0:
        if dp[i][0]>dp[i//2][0]: dp[i]=[dp[i//2][0]+1,i//2]
    if i%3==0:
        if dp[i][0]>dp[i//3][0]: dp[i]=[dp[i//3][0]+1,i//3]

a,b=dp[-1][0],dp[-1][1]
print(dp[-1][0])
print(n,end=' ')
while a!=0:
    print(b,end=' ')
    a,b=dp[b][0],dp[b][1]

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]