[백준(BOJ)] #1463- 1로 만들기 (파이썬, Python3)

문제

 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

---

문제 풀이

이 문제는 동적 계획법을 사용하여 풀 수 있습니다.

 

2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

 

처음에 이 문제를 보고 3이나 2로 나누는 것을 우선으로 적용시키는 그리디 알고리즘으로 접근할 수 있지 않을까 생각을 해봤습니다(1로 더 빠르게 접근할 수 있기 때문에). 하지만 이럴 경우 문제 예시와 같이 10이 입력될 경우

 

10 -> 5 -> 4 -> 2 -> 1

 

로 연산이 총 네번 적용됩니다.

 

10 -> 9 -> 3 -> 1

 

이와 같이 총 세번의 연산으로 1을 만들 수 있는 방법이 있는데 말이죠. 따라서 그리디 알고리즘의 조건에서 최적 부분 구조의 조건을 만족하지 못합니다.

 

따라서 이 문제를 동적 계획법으로 접근하였고 다음과 같은 방법으로 과정을 생각했습니다.

 

1) 연산 횟수를 값으로 갖는 dp 테이블을 만든다.

 

2) 2부터 Bottom-Up 방식으로 다음과 같이 횟수를 최적화시킨다.

 

먼저 횟수는 이전 값에 1을 더해줌. n에서 1로 만드는 과정에서 1을 빼는 연산의 반대 과정으로 부분 문제에서 1을 만드는 연산의 최댓값을 나타냄.

 

해당 숫자가 3이나 2의 배수이면 3이나 2로 나눈 숫자의 연산 횟수에서 1을 더한 값이랑 위에서 구한 이전 값에 1을 더해준 값을 비교해서 더 작은 값으로 갱신.

 

 

ex) n = 10

 

 

위와 같은 알고리즘은 동적 계획법의 조건인 최적 부분 구조와 겹치는 부분 문제를 만족하게 됩니다.

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    # dp 테이블
    dp = [0] * (n+1)

    # Bottom-Up
    for i in range(2, n+1):
        # 일단 1을 더한다. 부분 문제의 최대 연산
        dp[i] = dp[i-1] + 1

        # 3의 배수이면 3으로 나눈 숫자의 연산 횟수가에 1을 더한 값과
        # 위에서 구한 값을 비교해서 더 작은 값으로 갱신
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i//3] + 1)
        # 2의 배수인 경우도 적용
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i//2] + 1)

    print(dp[n])

결과