[BOJ] 1463 - 1로 만들기

정리중...

이 문제는 처음 볼 때부터 풀고 나서까지 머리에 물음표만 가득했다.

나름 처음부터 정리하며 문제를 풀어갔고, 첫 번째로 틀린 이후로 반례도 잘 찾아냈다고 생각했는데 또 틀렸다.

이건 고민해봐도 답없겠다 싶어서 반례나 보려고 질문 게시판으로 들어갔는데

반례나 코드 오류 있으면 찾아주세요..ㅠㅠ

아니 이걸 제가 어떻게 찾아요..

---

답은 DP에 있다

Dynamic Programming은 특정한 알고리즘은 아니고, 문제 해결방법으로 볼 수 있다.

큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 하는 방법을 사용한다.

기억하며 풀기

DP의 사용 조건

1. Overlapping Subproblems
   DP는 부분 문제의 결과를 저장하여 재사용함으로써 같은 문제를 재 계산하지 않아야 한다.
   부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하므로 DP를 사용할 수 없다.

2. Optinal Substructure
   부분 문제의 최적 결과값을 사용해 전체 문제의 최적 결과값을 낼 수 있어야 한다.
   
   

DP 구현방법

1. Bottom-Up (Tabulation)
   dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용 하는 방식이다.
   table에 저장된 값에 직접 접근하여 재활용한다.
   결과값을 기억하고 재활용한다.
   반복문을 사용하여 구현한다.

2. Top-Down (Memoization)
   dp[n]의 값을 찾기 위해 위에서부터 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과값을 재귀를 통해 전이시켜 재활용하는 방식이다.
   이미 전에 계산을 완료한 경우 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다.
   재귀를 사용하여 구현한다.

---

문제 풀이

n = int(input())
cntList = [0] * (n+1)

for i in range(2, n+1):
    cntList[i] = cntList[i-1] + 1

    if i%2==0:
        cntList[i] = min(cntList[i], cntList[i//2]+1)
    if i%3==0:
        cntList[i] = min(cntList[i], cntList[i//3]+1)
print(cntList[n])

bottom-up 방식으로 풀 수 있다.

---

참고자료

알고리즘 - Dynamic Programming(동적 계획법)
[파이썬] 백준 - 1463: 1로 만들기 (매우 자세한 해설 포함)