[Python/파이썬] 백준 알고리즘 1463번 - 1로 만들기 (동적 계획법 / 다이나믹 프로그래밍 풀이)

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

 

 

 

<풀이>

이 문제는 전에 결과를 다음 결과에 이용하는 Dynamic Programming(동적 계획법) 문제이다.

 

힌트를 보면 정수 X가 10인 경우 10 -> 9 -> 3 -> 1 의 과정으로 1이 된다고 했는데,

10은 정수 X가 9인 경우의 횟수에 +1을 한 값이고

9는 정수 X가 3인 경우의 횟수에 +1을 한 값이고

3은 정수 X가 1인 경우의 횟수에 +1을 한 값이다.

 

다시 말해서 10을 구할 때는 9의 결과를, 9를 구할 때는 3의 결과를 이용한다.

 

따라서 아래의 조건을 만족하기 때문에,

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일하다.

동적 계획법을 사용할 수 있다.

 

동적 계획법의 가장 핵심적인 내용은 메모이제이션(Memoization)이었다.

해당 내용들에 대해 자세히 알고 싶다면 아래 링크를 보면 된다.

https://kbwplace.tistory.com/91

다이나믹 프로그래밍(Dynamic Programming)이란 (동적 계획법 / 동적 프로그래밍)

 

이제 동적 계획법을 이용한 풀이를 보겠다.

N = int(input())

# Memoization 부분
# (N이 아니라 N+1인 이유는 인덱스 1부터 사용하기 때문이다.)
dp = [0] * (N + 1)

# i가 1인 경우는 연산을 사용하는 횟수가 0회이므로 i는 2부터 시작한다.
for i in range(2, N+1):
    # 정수 i에 사용하는 연산을 1을 빼는 것으로 하는 경우
    dp[i] = dp[i-1] + 1
    
    # 정수 i에 사용하는 연산을 2를 나누는 것으로 하는 경우
    if i % 2 == 0:
        # 1을 빼는 것으로 했을때와 2를 나누는 것으로 했을 때 중에서
        # 더 적게 연산을 사용하는 경우를 선택해서 dp[i]에 넣는다.
        # (dp[i//2]에 +1을 하는 이유는 dp[i//2]의 횟수에 i에서 i//2로 가는데 사용한 연산 횟수 1도 더해줘야하기 때문이다.)
        dp[i] = min(dp[i], dp[i//2]+1) 
        
    # 정수 i에 사용하는 연산을 3를 나누는 것으로 하는 경우
    if i % 3 == 0:
        # 1을 빼는 것으로 했을때, 2를 나누는 것으로 했을 때와 3을 나누는 것으로 했을 때 중에서
        # 더 적게 연산을 사용하는 경우를 선택해서 dp[i]에 넣는다.
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[N])

dp라는 리스트를 N+1만큼 0으로 초기화를 시켜 만들고, for문을 통해 N번 인덱스까지 접근한다.

dp[i] = dp[i-1] + 1 코드를 통해 dp[i]에 먼저 1을 뺐을 때의 연산인 경우를 가정한다.

 

그리고 각각의 if문들을 통해 각각 2, 3으로 나누어 떨어지는 경우 dp[i]값과 비교해 더 작은 값을 다시 dp[i]에 넣는다.

 

이렇게 하면 문제에서 주어진 아래 세 가지 경우를 모두 조사하게 된다.

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

그리고 이 세 가지 연산의 경우를 조사하며 min()함수로 최소 횟수를 구하므로 문제에서 원하는 값을 구할 수 있다.

 

 

이 코드에서 하나 유념할 점은 if-else문을 사용하지 않았다는 것이다.

1을 뺀 경우, 3으로 나눈 경우, 2로 나눈 경우를 모두 조사해봐야하므로 if문을 여러번 사용해준다.

 

 

 

<핵심 정리>

1. 동적 계획법의 핵심은 배열을 이용한 메모이제이션(Memoization)이다.

2. 인덱스의 수 자체를 문제에서 사용하면 더 편한 경우 인덱스 0번은 비워두고 사용해도 된다.

3. if문을 여러번 사용해 배열의 값과 비교하며 모든 경우를 다 조사할 수 있다. (if-else문 사용 X)