14631 [백준] 1463 - 1로 만들기, C++ https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 본 문제는 DP 문제로 D[n] = min(D[n-1], D[n/3], D[n/2]) + 1 (n이 2 또는 3으로 나눌 수 있을 때의 점화식을 정의할 수 있다. DP문제는 중복되는 계산이 여러 번 등장하여야 하고, 큰 문제를 작은 문제에서 답을 구할 수 있어야 한다. 이때, 모든 반복되는 계산은 1번만 하도록 하여 계산 속도를 높인다. n을 1로 뺀 경우의 수 계산하여 저장 n을 3으로 나눌 수 있을 때, n을 3으로 나눈 경우의 수와 1번을 비교하여 저장 n을 2로 나눌 수 있을 때, n을 2로 나눈 경우의.. 2020. 1. 10. 이전 1 다음