[백준] 1463. 1로 만들기
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
예제 입력 1
1
2
예제 출력 1
1
1
예제 입력 2
1
10
예제 출력 2
1
3
풀이
이 문제의 목표는 정수 N이 주어졌을 때, 위와 세 연산을 적절히 사용해서 1을 만드는데 필요한 연산 횟수의 최소값을 출력하는 문제이다.
최솟값.. 이런식으로 최소값을 구하는 문제는 내 경험에 의하면 푸는 방법이 두 가지로 나뉜다.
- 모든 경우의 수를 다 확인하여 최소값을 구하는 방식
- 제한조건들로 인해 생기는 수의 패턴을 파악하고 이를 활용하여 최소값을 구하는 방식
따라서 간단하게 생각하면 정수 N을 1로 만드는 모든 방법을 다 써본다음에 그때의 필요한 연산횟수의 최소값을 출력하여 문제를 풀 수 있어보인다.
(사실 생각하기는 간단하지만 구현하려고 하면 만만치 않아보인다.)
근데 여기서 다시 문제로 올라가보면 정수 N을 1로 만들기 위해 지켜야하는 엄격한 규칙이 무려 세 가지나 보인다.
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
이 조건들로 인해 생기는 정수 N의 따른 최소 연산 횟수에 어떤 패턴이 있을지 파악해보자.
먼저 1번 규칙, X가 3으로 나누어 떨어지면 3으로 나눈다.
즉, N=9면 3으로 나누고, N=6이면 3으로 나눈다라는 뜻이다.
그 다음 2번 규칙, X가 2로 나누어 떨어지면 2로 나눈다.
N=4면 2로 나누고, N=6이면 2로 나누라는 뜻이다.
여기서 혼란이 발생한다.
N=6일 때는 2로 나누어야할까 아니면 3으로 나누어야 할까?
정답은 바로 연산 횟수가 최소값이 되는 것으로 나누어야 한다는 것이다.
예시를 들자면 만약 N=24라고 했을 때, 24/2와 24/3중 연산 횟수를 최소값이 나오는 것으로 고르는 것이다.
즉 이는 과거의 값을 저장하여 나중에 사용하는 Dynamic programming 문제이다.
그럼 24/2와 24/3중 어떤게 최소값이 나오는지 알 수 있을까?
N=12, 24라고 하고, f를 연산횟수를 구하는 함수라고 하자. N=12일 때와 같은 방법으로 N=24을 1로 만든다고 가정하면 N=24일 때 연산횟수는 무엇인가?
바로 f(24/2) + 1이 된다. 24를 2로 나눈것이 12이기 때문에 이때의 연산 횟수는 단순하게 12를 1로 만드는 연산 횟수에 1을 더해주면 된다는 것이다.
이것을 똑같이 24를 3으로 나누는 것에 대해서도 적용하면 f(24/3) + 1이 연산횟수가 된다.
따라서 우리가 해야할 것은 f(24/2) + 1, f(24/3) + 1 중에서 더 작은 값을 알아내면 되는 것이다.
예외로 만약 2와 3으로 나누어떨어지지 않는 수는 어떤가?
3번 규칙에 따르면 N이 2와 3으로 나누어 떨어지지 않을 경우 1을 뺀다.
즉, 만약 N=13이라고 한다면 f(13) = f(12) + 1이 되는 것 이다.
위에서 찾은 모든 패턴을 코드로 구현하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
a = int(input())
dp = [0] * a+1
for idx in range(2, a+1):
dp[idx] = dp[idx-1] + 1
if idx % 2 == 0:
dp[idx] = min(dp[idx], dp[idx//2]+1)
elif idx % 3 == 0:
dp[idx] = min(dp[idx], dp[idx//3]+2)
print(dp[a])