[BOJ] 1로 만들기_1463

정답 코드

위 문제는 전형적인 DP문제이다.

우선 문제를 리뷰하기 전에 DP의 탑다운 방식과 바텀업 방식의 차이에 대해 짚고 넘어가자.

 

동적 계획법이란?

큰 문제를 작은 문제들로 나누어 푸는 것을 일컫는 말이다.

 

동적 프로그래밍 방법

작은 문제로 나누어 해결할 떄, 중복된 값을 구하지 않고 메모제이션 하는 것이다.

 

 

메모제이션을 하는 방식과, 그렇지 않은 방식에 대해 설명하겠다.

 

F는 피보나치 함수이다.

메모제이션을 하지 않고, 탑 다운 방식으로 피보나치 수열을 구한다면 작은 단위의 값을 반복해서 여러번 계산해야 한다.

이를 바텀업 방식으로 해결할 수 있다.

 

위와 같이 작은 단위의 값을 배열에 저장하여, 해당 값이 필요할 떄 작은 단위를 반복하여 계산하지 않게 된다.

 

1로 만들기 문제도 이러한 방식으로 해결할 수 있다.

 

낮은 값부터 올라가진 않지만, 미리 n+1값을 모든 배열에 대입한다.

n+1을 대입하는 이유는 해당 값보다 작은 값이 나올 수 없기 떄문이다. (즉, 아직 계산된 값이 들어가지 않았다면 n+1값이 들어 있을 것이고 , 처음 계산된 값을 넣을 때 n+1보다 클 수 없기 떄문이다.)

 

이러한 방식으로 해당 값들을 배열에 저장하여 그보다 작은 값이 있다면 교체해서 구하였다.