12852 백준 파이썬

수를 1로 만드는 최소값을 구하되, 만드는 방법도 출력하라는 문제

 

간단하게 최소 방법은

3으로 나눠지면 3으로 나눈 dp값과 현재값을 비교해서 초기화,

2로 나눠지면 2로 나눈 dp값과 현재 값을 비교해서 초기화,

둘다 안되면 -1한 dp값과 현재 값을 비교해서 초기화.

 

문제는 방법이다.

나는 m이라는 2차원 리스트를 만들어서 dp값을 초기화 할때 그 값에 맞춰서 이전 경로를 추가하고, 이전 숫자를 추가하는 식으로 경로를 저장했다.

 

출력시에는 출력하는 숫자+m에 저장된 경로를 출력시켰다.

n=int(input())
dp=[99999999 for x in range(n+4)]
m=[[] for x in range(n+4)]
dp[0],dp[1]=0,0
dp[2],dp[3]=1,1
m[0]=[0]
m[1]=[1]
m[2]=[1]
m[3]=[1]
if n>3:
    for x in range(4,n+1):
        if x%3==0:
            dp[x]=min(dp[x],dp[x//3]+1)
            if dp[x]==dp[x//3]+1:
                k=x//3
        if x%2==0:
            dp[x]=min(dp[x],dp[x//2]+1)
            if dp[x]==dp[x//2]+1:
                k=x//2
        dp[x]=min(dp[x],dp[x-1]+1)
        if dp[x]==dp[x-1]+1:
            k=x-1
        m[x].extend(m[k])
        m[x].extend([k])
print(dp[n])
if n!=1:
    print(n, end=' ')
for x in reversed(m[n]):
    print(x, end=' ')