백준 1463 [파이썬]

문제 Note 3, 2로 나누기, 1 빼기로 하는데 2로 나누는 건 1 또는 2를 빼서 3의 배수를 만들어 나눠주는 게 더 빠르니 안 해줘도 되지 않을까? Code n = int(input()) d = [0] * (n + 1) for i in range(2, n + 1): d[i] = d[i - 1] + 1 if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) print(d[n]) 다이나믹 프로그래밍(동적 계획법)을 이용해야 한다.

피보나치 문제도 이와 같은 방식으로 풀 수 있다. n = int(input()) d = [0] * (n + 1) 우선 정수 n을 입력 받고, 동적 계획법을 사용할 테이블을 만들어준다. 여기서 각 정수와 리스트의 인덱스를 동일하게 만들어주기 위해서 n+1 크기로 만든다. for i in range(2, n + 1): d[i] = d[i - 1]...