[BOJ/백준 - 1463] 1로 만들기

문제 출처: https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

---

 

DP 단계별 풀어보기 카테고리에 등록된 문제로 

DP 로 해결하자

 

일단 문제 예시 input인 10을 보자

이걸 10부터 찾아갈라는걸 공책에 손으로 해봐도 경우의 수가 좀 생기는 것을 알 수 있다

 

그럼 이걸 풀 때 input값에 어떤 연산을 하든 말든 상관없이 '최소한'의 연산을 하자는 것을 생각하자

 

이하 연산의 종류는 알파벳으로 그냥 적겠다

x: 3나누기 연산

y: 2나누기 연산

z: 1빼기 연산

 

그냥 직관적으로 떠올릴 수 있는 곳까지

1부터 차례대로 올라가면서 1로 가는 연산의 횟수를 적어보자

 

1은 아무 연산없으니까 0

2는 y -> 1

     z -> 1

     종류는 모르지만 1번의 연산을 통해 1로 만들 수 있다

3은 x -> 1

4는 y -> 2 -> y -> 1

     y -> 2 -> z -> 1

     z -> 3 -> x -> 1

     어떤 경로로 갈진 모르지만 2번의 연산이 필요하다

 

4를 보면 4에다가 y나 z 연산을 한번만 적용하면 2와 3으로 간다는 것을 알 수 있고

2와 3은 1로 가기 위한 최소 연산 횟수를 구해놓았기 때문에 

그 둘중에 더 작은값에 1을 더하면 4의 연산 횟수를 알 수 있다.