해킹왕 양선규

x = int(input()) d = [0] * (x + 2) d[1] = 1 d[2] = 1 for i in range(3, x + 1): d[i] = d[i-1] + d[i-2] print(d[x]) 간단한 DP 문제이다. 재귀함수로 구현하면 입력값이 90까지이기 때문에 메모리가 터져버린다. x가 1, 2일 경우만 리스트에 등록해 둔 후 간단한 반복문을 돌리면 된다. 재귀 구현했을 경우 90이면 정말 컴퓨터가 터지기 직전까지 가는데 상향식 DP방식인 반복문으로 구현하면 대략 90번정도만 연산하면 되기 때문에 문제를 해결할 수 있다.

import sys input = sys.stdin.readline x = int(input()) d = [0] * (x + 1) path = ['' for _ in range(x + 1)] path[1] = '1' for i in range(2, x + 1): d[i] = d[i - 1] + 1 prev = i - 1 if i % 3 == 0 and d[i // 3] + 1

x = int(input()) d = [0] * ((10 ** 6) + 1) for i in range(2, x + 1): d[i] = d[i - 1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) print(d[x]) 다이나믹 프로그래밍 문제이다. d는 메모이제이션(값을 저장해 놓을)할 리스트. i는 현재 계산중인 숫자 d[i] 는 i에 대한 최소연산횟수이다. 숫자 2부터 바텀 업 방식으로 d리스트를 채워나가 최종적으로 x의 최소연산횟수를 구하는 것이다. 이 문제는 3가지 연산을 할 수 있다. 1을 빼기, 2로 나누기, 3으로 나누기 하지만 2나 3으로 나눠진다고 해서 무조건..