[PS] 백준 1463번 - 1로 만들기 | Python

백준 1463번 문제 write-up입니다.

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

1463번: 1로 만들기

---

문제에 주어진 연산을 이용하여 입력되는 수를 1로 만드는데, 이 연산을 사용하는 최솟값을 출력하면 됩니다.

주어진 연산은 다음과 같습니다.

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

직접 1로 만드는 경우의 수를 계산하게 되면 시간 초과가 나기 때문에, dynamic programming을 이용하여 문제를 풀어야 합니다.

 

 

dynamic programming에 관한 내용은 다음 게시물을 참고하시기 바랍니다.

https://spareone.tistory.com/73

[Algorithm] Dynamic Programming(동적 계획법)과 피보나치 수열

 

 

표를 이용하여 n=10일 때 연산 사용 개수를 작성해 보겠습니다.

n	1	2	3	4	5	6	7	8	9	10
연산	0	1	1	2	3	2	3	3	2	3

위 표를 분석하면 이렇게 점화식을 세울 수 있습니다.

3개의 식 중에 최솟값을 결과로 도출하면 됩니다.

점화식을 정리하면,

1. 3과 2 모두 나누어 떨어지지 않는 경우 : n-1의 결과에서 1을 더한 후 도출
2. 3과 2로 나누어 떨어지는 경우 : n-1의 결과에서 1을 더한 것, n/3의 결과에서 1을 더한 것, n/2의 결과에서 1을 더한 것 3개의 결과를 비교하여 최솟값 도출

 

1은 1이니 0번 사용하고, 2나 3은 나누면 1이기 때문에 1번 사용합니다.

4의 경우 4 → 3 → 1 또는 4 → 2 → 1이 나오는데 모두 연산 횟수가 2번으로 동일합니다.

5의 경우 5 → 4 → 3 → 1 총 3번의 연산을 사용합니다. 5는 2와 3의 서로소이기 때문에 무조건 -1을 한다고 보면 됩니다.

10의 경우 10 → 5 → 4 → 3 → 1 또는 10 → 9 → 3 → 1이 나옵니다.

후자가 3으로 연산 사용 횟수가 낮기 때문에 3번의 연산이 최솟값입니다.

 

위 점화식과 DP를 이용하여 코드를 작성하면 됩니다.

 

def solution(n):
    res = [0 for i in range(1000001)]
    res[2] = res[3] = 1

    if n <= 3:
        return res[n]
    
    for i in range(4, n + 1):
        if i % 3 != 0 and i % 2 != 0:
            res[i] = res[i - 1] + 1
        elif i % 2 == 0 and i % 3 == 0:
            res[i] = min(res[i - 1] + 1, res[i // 2] + 1, res[i // 3] + 1)
        elif i % 3 == 0:
            res[i] = min(res[i - 1] + 1, res[i // 3] + 1)
        elif i % 2 == 0:
            res[i] = min(res[i - 1] + 1, res[i // 2] + 1)

    return res[n]

if __name__ == "__main__":
    print(solution(int(input())))