[백준 BOJ_12852] 1로 만들기 2 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법으로 풀었습니다.

cache는 다음과 같습니다.

cache[i][0] = 1에서 정수 i까지 만드는데 드는 최소 연산의 숫자
cache[i][1] = 1에서 정수 i까지 만드는데 거친 숫자들의 list

N에서 출발하는 것이 아닌 1부터 출발하여 N까지 도달하게끔 했습니다. 세 가지 경우를 차례로 확인해주면서 cache를 갱신해줍니다.

1을 더해주는 것 이외에는 2나 3으로 나누어 떨어지는지, 그리고 해당 연산을 하는 것이 최소한의 연산인지를 확인해준 뒤 갱신해주어야 합니다.

마지막에는 cache[N][0](1에서 N까지 만드는데 드는 최소 연산의 숫자)와 cache[N][1](1에서 N까지 만드는데 거친 숫자들의 list)을 뒤집어 출력해줍니다.

코드

N = int(input())

cache = [[0, []] for _ in range(N+1)]
cache[1][0] = 0
cache[1][1] = [1]
if N > 1:
  for i in range(2, N+1):
    cache[i][0] = cache[i-1][0] + 1
    cache[i][1] = cache[i-1][1] + [i]
    if i % 3 == 0 and cache[i][0] > cache[i//3][0] + 1:
      cache[i][0] = cache[i//3][0] + 1
      cache[i][1] = cache[i//3][1] + [i]
    if i % 2 == 0 and cache[i][0] > cache[i//2][0] + 1:
      cache[i][0] = cache[i//2][0] + 1
      cache[i][1] = cache[i//2][1] + [i]

print(cache[N][0])
print(*cache[N][1][::-1], sep=" ")