Backjoon 12852번 1로 만들기 2

백준 알고리즘

• 12852번 1로 만들기 2

---

파이썬을 사용하였습니다.

단계별로 풀어보기 동적 계획법과 최단거리 역추적에 1번째 문제로 분류되어있는 문제입니다.

---

• 입력
  1. 입력 X 를 받습니다.
  2. X를 3으로 나누는 방법, 2로 나누는 방법, 1을 빼는 방법의 연산을 사용해 X를 1로 만듭니다.
  3. X를 1로 만드는데 가장 적게 연산한 방법을 찾아 출력합니다.
     
     

---

저는 파이썬의 리스트를 이용해서 풀었습니다.
리스트를 순회 하며 나타날수 있는 경우를 모두 출력합니다.
리스트의 마지막에 3,2,1이 등장한다면 재귀를 종료합니다.

---

정답 코드

import sys
sys.setrecursionlimit(10**6)

def sol(n):
    te = []
    for i in n:
        if i[-1]==1:
            return i
        elif i[-1]==2 or i[-1]==3:
            i.append(1)
            return i
        else:
            temp = []
            if i[-1]%3==0:
                temp.append(i+[i[-1]//3])
            if i[-1]%2==0:
                temp.append(i+[i[-1]//2])
            temp.append(i + [i[-1] -1])
        te.extend(temp)

    return sol(te)
n = int(input())
answer = [[n]]
answer = sol(answer)
print(len(answer)-1)
for i in answer:
    print(i,end=' ')