문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
코드
#include <iostream> #include <algorithm> using namespace std; int N; // 이 문제는 n을 규칙을 사용하여 나누면 또 다른 n에 대한 문제가 된다. // 따라서 메모이제이션할 부분은 각 숫자에 대한 횟수이다. int Memo[1000001]; int dp(int n) { // 점화식은 다음과 같다. // Memo[n] = min(Memo[n - 1] + 1, Memo[n / 2] + 1 if n % 2 == 0, Memo[n / 3] + 1 if n % 3 == 0) // 이미 메모이제이션 된 부분은 그대로 사용한다. if (Memo[n] || n < 2) return Memo[n]; // 점화식에 따라 코드를 작성한다. Memo[n] = dp(n - 1) + 1; if (n % 2 == 0) Memo[n] = min(Memo[n], dp(n / 2) + 1); if (n % 3 == 0) Memo[n] = min(Memo[n], dp(n / 3) + 1); return Memo[n]; } int main() { ios::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); // 메모이제이션 for (int i = 2; i <= 1000000; ++i) dp(i); cin >> N; cout << Memo[N]; } |
#include <iostream> #include <algorithm> using namespace std; int N; int dp(int n) { // 이 문제는 좀 더 최적화 할 수 있다. // 조금만 더 고찰해보면 1을 만들기 위해서는 // 1을 빼는 것보단 2나 3으로 숫자를 나누는 것이 훨씬 빠르다. // 따라서, 1을 빼는 경우는 2나 3으로 나누어 떨어지지 않는 경우이다. // 이를 코드로 옮기면 아래와 같다. return (n < 2) ? 0 : // n % 2와 n % 3을 하는 이유는 1을 빼는 것과 같기 때문이다. min(dp(n / 2) + n % 2, dp(n / 3) + n % 3) + 1; } int main() { ios::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); cin >> N; cout << dp(N); } |
using System; namespace ForAlgoCsharp { class Program { static void Main(string[] args) { int n = Convert.ToInt32(Console.ReadLine()); Console.Write(dp(n)); } static int dp(int n) { return (n < 2) ? 0 : Math.Min(dp(n / 2) + n % 2, dp(n / 3) + n % 3) + 1; } } } |
N = int(input()) def dp(n): return 0 if n < 2 else min(dp(n // 2) + n % 2, dp(n // 3) + n % 3) + 1 print(dp(N)) |
복기
DP 문제 중 처음으로 솔루션을 보지 않고 푼 문제라서 뿌듯하다. 솔직히 저기서 더 최적화가 이뤄질 줄은 몰랐는데, 다음에는 좀 더 고찰해봐야겠다.