백준 알고리즘 1463번

1로 만들기 성공 풀이

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	30658	9750	6534	33.225%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최소값을 출력한다.

예제 입력 

2

예제 출력 

1

예제 입력 2 

10

예제 출력 2 

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

#############################################################################

우선 문제를 풀기 전에 어떤 알고리즘을 활용해서 풀어야할지부터 생각해야한다.

여기서는 연산을 활용한 최소값을 묻고있다.

예를 들어 10의 최소값을 구하려면 첫 단계로 연산 두 가지가 가능하다.

1. 2로 나눠본다.

2. 1을 빼본다. 

만약 2번을 선택해서 1을 뺀다면 9가 되고 9에서의 최소 연산값을 구해야한다. 그런데 여기서 9의 최소 연산 개수를

구하려고 해도 경우의 수가 1을 빼거나 3으로 나누는 2가지 경우의 수가 생긴다.

만약 9의 최소 연산 횟수를 알고있다면 ?

1을 빼는 연산횟수 + 9의 최소 연산 횟수 = 10의 최소 연산횟수 가 된다. 

그렇다면 9의 최소 연산 횟수는 어떻게 알고있을까?

9도 마찬가지로 전 단계의 최소 연산횟수가 필요하다.

그렇게 계속 거슬러 올라가다보면 결국 2와 3에서 시작되는 것을 알 수 있다. 이렇게 작은 해답에서 점점 큰 해답을

구할 때 쓰는 것이 동적프로그래밍이다.

※ 동적프로그래밍이 쓰이는 문제들은 대부분 이렇게 각 단계마다의 여러 경우의 수가 존재하고

그중에 최소값이나 최대값을 저장하고 있어야할 경우 동적프로그래밍이 쓰이는 것 같다.

동적 프로그래밍(Dynamic Programming)을 이용하여 문제 풀기

이제 어떤 알고리즘을 사용하여 풀어야하는지 파악했으니, 본격적으로 문제를 풀어보자.

1. 우선 각 단계의 최소 연산 개수를 저장할 리스트를 생성한다.

2. 각 단계마다 일어날 수 있는 경우의 수를 계산해서 그 중 가장 작은 연산 값을 저장한다.

동적프로그래밍을 이용하여 푸는 것을 눈치채더라도, 2번의 경우의 수를 모두 알아내 점화식을 세우는 것이 어렵다.

하지만 이 문제는 점화식을 세우는 것이 간단한 편이다.

각 단계마다 일어날 수 있는 경우의 수는 총 3가지이다. 이 3가지 중 가장 작은 값이 그 단계의 결과값이 된다.

1. dp[i - 1] + 1 : 1을 빼고 최소의 연산 개수를 구하는 경우

2. dp[i / 2] + 1 : 2로 나누고 최소의 연산 개수를 구하는 경우

3. dp[i / 3] + 1 : 3으로 나누고 최소의 연산 개수를 구하는 경우

2로 나눠진다면 2로 나눈 경우의 수도 구하고, 3으로 나눠진다면 3으로 나눈 경우의 수를 구해서 그 중 가장 작은 값을

저장하면된다.

n = int(input())

dp = []

dp.append(0) # 0
dp.append(0) # 1
dp.append(1) # 2
dp.append(1) # 3

for i in range(4, n + 1):
    dp.append(dp[i - 1] + 1); # 1을 빼고 최소 연산의 개수 계산

    if(i % 2 == 0): # 2로 나눠진다면
        dp[i] = min(dp[i], dp[i // 2] + 1) # 비교
    if(i % 3 == 0): # 3으로 나눠진다면
        dp[i] = min(dp[i], dp[i // 3] + 1) # 비교

print(dp[n])