1로 만들기 - (Dynamic programming - 동적계획법) ★☆☆

 

이 문제는 약간의 시행착오가 있었다.

 

처음에 문제와 같은 방식으로 1로 만들어나가는 재귀함수 방식을 택했는데,

깊이가 너무 깊었는지 제대로 돌아가지 않았다.

그래서 for문을 사용해서 코드를 작성하니 간단하게 해결하였다.

 

1부터 시작해서 세가지의 선택지가 있다.

a. 2를 곱하기

b. 3을 곱하기

c. 1을 더하기

위 시행을 하면 연산을 한번 한 것이므로 1을 더해준다.

 

2를 곱하는 것을 예로 들면,

10에서 2를 곱하면 20이다.

20이 만들어지는 최소연산값이 dp[20]에 들어있는데, dp[10] + 1을 한 값과 dp[20]을 비교하여 더 작은 값을 dp[20]에 넣는다.

그렇다면 dp[20]은 항상 작은 값을 갖게 된다. (b,c 연산도 마찬가지)

 

여기서 중요한 것은 i*2, i*3, i+1이 n의 범위를 넘지 말아야 한다는 것이다. (그래서 if문을 사용했다.)

 

위 코드는 실패한 재귀함수 버전이다.

depth limit를 초과했다고 나온다. (풀어주면 되지만 이미 시간상 비효율적인 듯하다)