dp

백준 1463(1로 만들기)

이제 본격적으로 dp 를 공부하면서 만난 첫번째 문제이다. top-down 방식으로 풀기를 원했지만 재귀가 아직 익숙하지 않아 bottom-up 으로 풀었다. 핵심로직은 2가지 이다. 1. 이전의 값을 이용해서 풀어야 한다. 2. 최초로 들어가 있던 값이 최소가 아닐 수 있다. #include #include using namespace std; int dp[3000001]; int X; void dpFunc(int X) { for (int i = 1; i dp[i] + 1) { dp[i * 3] = dp[i] + 1; } if (dp[i * 2] > dp[i] + 1) { dp[i * 2] = dp[i] + 1; } if (dp[i + 1] > dp[i] + 1) { dp[i + 1] = dp[i] +..