[백준(BOJ)] 1463번 : 1로 만들기 - PYTHON[파이썬]

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

---

 

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍

 

 

---

 

⊙ 문제 접근 과정

 

처음에는 간단하게 문제에 접근하여 코드를 구현해봤다.

 

하지만 결과는 실패!! 단순 구현 문제가 아니라 다이나믹 프로그래밍 알고리즘으로 풀어야했다!

 

아래에 있는 힌트를 보니 단순 구현의 경우 10일 때 예외가 존재했다.

 

아래는 첫 번째로 푼 단순 구현 코드이다.

 

X = int(input())
count = 0

while(X!=1):  
    if(X%3==0):
        X=X/3
    elif(X%2==0):
        X=X/2
    else:
        X=X-1
    count = count + 1
    print(count)
    print(X)

print(count)

 

결과는 4로 나온다. 하지만 최소 경로를 원하는 이 문제에 경우엔 3이 나온다.

10 -> 9 -> 3 -> 1이다.

 

참고로 위 단순 구현의 경우 10 -> 5 -> 4-> 2 -> 1이다.

 

 

다이나믹 프로그래밍이 무엇인지는 나중에 따로 포스팅하도록 하겠다.

 

우선 문제에서 원하는 3으로 나누어 떨어질 때, 2로 나누어 떨어질 때, 1을 뺄 때, 총 3가지로 나누어 문제를 풀어보자

 

식으로 표현하면 N//3, N//2, N-1이다.

 

---

 

⊙ 문제 풀이

 

N = int(input())

X = [0 for _ in range(N+1)]

for i in range(1, N+1):
    if i == 1:
        X[i] == 0
        continue
    
    X[i] = X[i-1] + 1

    if i % 3 == 0 and X[i//3] + 1 < X[i]:
        X[i] = X[i//3] + 1
    if i % 2 == 0 and X[i//2] + 1< X[i]:
        X[i] = X[i//2] + 1

print(X[N])

 

---

⊙ 결과

 

---

 

 

⊙ 마무리

 

 

다이나믹 프로그래밍(DP) 문제를 많이 접한 후 DP 알고리즘에 대해 포스팅하려고 한다.