백준1463 (1) 썸네일형 리스트형 [Algorithm] 백준 1463 1로 만들기 c++ https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 DP N에서 1을 만드는 방법을 생각하지 않고, 1에서 N을 만드는 방법으로 구현한다. (bottom-up) N = 1인 경우 f[1]에 0을 넣고(basecase) 1에서 +1, *2, *3을 했을 때의 값인 f[2], f[3]에 1(f[1] + 1)을 넣는다. 즉, f[i+1] = f[i*2] = f[i*3] = f[i] + 1 이다. 다만 i보다 더 큰 수(j)로부터 최소의 횟수를 만들 수 있으므로 min(f[i] + 1(현재값), f[j] + 1)으로 값을 업데이트한다. 주의사항) 1에서 N이 되는.. 이전 1 다음