https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
다이나믹 프로그래밍을 활용하는 문제이다.
다이나믹 프로그래밍은 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다.
분할정복 문제와도 비슷한데 다른 점은 다이나믹 프로그래밍은 겹치는 문제가 발생하기 때문에 메모이제이션 등이 필요하다.
이미 계산한 정보를 배열에 저장하여 나중에 동일한 계산을 해야할 때 저장된 값을 반환한다.
첫번째는 top-down 방식으로 작성하였다.
계산한 정보를 저장할 배열을 d라고 했고 1000001 크기를 가지도록 했다.
f(n)이 최소횟수라 하자.
f(n)=min{ 0 (n==1)
f(n/3)+1 (n%3==0)
f(n/2)+1 (n%2==0)
f(n-1)+1}
이 점화식이 된다.
n==1이면 종료조건으로 0을 반환한다.
d[n]이 0이 아니면 이것은 d[n]에 값이 저장되어있다는 뜻이다. 따라서 d[n]의 값이 있으면 그냥 반환하면 된다.
3이나 2로 나누는 것이 n-1하는것 보다 작은값이라고 확정할수 없다. 또한, 이 반대도 확정할 수 없다.
따라서 작은 값을 반환하는 min 함수를 이용하여 작은값을 반환하고 이를 배열(d[n])에 저장해준다. 그리고 이 값을 반환한다.
두번째는 bottom-up 방식이다.
i가 2부터 n까지 for문이 돌아간다. 2부터 시작하는 이유는 n==1일때 0이기 때문에 2부터 시작한다.
위의 방식과 똑같다.
먼저 d[i]에 d[i-1]+1한것을 넣어준다. 그러나 1을 뺀것과 3또는 2로 나눈것 중 무엇이 최소가 될지 모른다
따라서 i가 3으로 나누어질때, 2로 나누어 질때 각각 min함수를 이용하여 d[i]와 d[i/3]+1(d[i/2]+1)을 비교하여 d[i]에 넣어준다.
이런식으로 n까지 한다면 배열을 통하여 저장된 값을 이용하여 d[n]을 구할 수 있다.
※dp[1000001] 해주는 이유 :1 0^6은 100만. 또한, dp[n]으로 접근할 거라면 100만 1개를 할당해줘야 인덱스를 벗어나지 않는다. (n-1로 접근한다면 dp[1000000]로 해줘도 된다.)
참고한 문서:
https://www.acmicpc.net/board/view/19169
https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221233570962
