[C#] 백준 1463 1로 만들기
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
예제 입력 1 복사
2
예제 출력 1 복사
1
예제 입력 2 복사
10
예제 출력 2 복사
3
힌트
10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.
문제 풀이
점화식에 관련된 문제이다. 하지만 점화식을 설명할 정도로 잘 알지는 못하고 dp와 같이 현재 상태를 이전 상태를 통해 알 수 있다는 점에 대해서정도로 간단하게만 알고 있다.
문제에 접근하는데 어려움을 느껴 메모장에 직접 10까지 어떤 방식으로 돌아가는지 나열해 보았다.
1 = 0
2 -> 1 = 1
3 -> 1 = 1
4 -> 2 -> 1 = 2
5 -> 4 -> 2 -> 1 = 3
6 -> 2 -> 1 = 2
7 -> 6 -> 2 -> 1 = 3
8 -> 4 -> 2 -> 1 = 3
9 -> 3 -> 1 = 2
10 -> 9 -> 3 -> 1 = 3
뭔가 규칙이 보일듯 말듯 한다.
그렇다면 이런식으로 생각하면 어떤가
1. 1을 빼야하는 경우
5, 7, 10의 경우 1을 빼야 계산이 가능하다. 즉, 1을 빼는 횟수가 한번 들어가면서 이후 그 이전의 상태 횟수와 같게 된다.
그렇다면 1을 빼는 횟수 (+ 1) 을 이전의 상태에 해주면 해당 값은 계산이 된다.
10의 경우 10 - 1을 하는 것(1) + 9의 횟수(2) = 3 이런 방식이다.
2. 3으로 나눠야 하는 경우, 2로 나눠야 하는 경우
2로 나누거나 3으로 나누거나 같으니 한번에 묶어서 하도록 하겠다.
만약 9라고 가정하면 3으로 나누고 나온 값의 횟수에 3으로 나누는 행위를 더해주면 된다. 위의 빼기와 동일하다.
즉 9 / 3 을 하는 것(1) + 3의 횟수(1) = 2 이다.
2로 나누는것도 마찬가지이다.
그러니 이 문제의 핵심은 나누거나 빼는 행위를 하여 이전 상태에서 이 행위를 한번 더해주는 것이 핵심이다.
문제 정답
using System;
using System.Collections.Generic;
using System.Numerics;
class Program
{
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
int[] dp = new int[n + 1];
for(int i = 2; i <= n; i++)
{
dp[i] = dp[i - 1] + 1;
if (i % 3 == 0)
dp[i] = Math.Min(dp[i], dp[i / 3] + 1);
if (i % 2 == 0)
dp[i] = Math.Min(dp[i], dp[i / 2] + 1);
}
Console.WriteLine(dp[n]);
}
}
1을 빼주는 것을 디폴트로 하고 나눠서 3으로 나누거나 2로 나눴을 때와 비교해서 최소값을 출력해주면 된다.
회고
DP는 하면 할 수록 어려운 거 같고 직접 손으로 시행횟수를 해봐야 어느정도 눈에 들어오는 거 같긴 하다. 그리고 식을 찾는 것도 쉽지 않다고 생각이 든다.