백준 1463 1로 만들기

* 다시 풀어볼 : 파티 
* (26)추가 리스트 : 1916(Boj1916dij2) , 9465(Boj9464), 1261(Boj1261dp2) 
* (27)추가 리스트 : 1904(Boj1904dp2), 2139(Boj2139dp) ,2638(Boj2638dfs2)
* (28)추가 리스트 : 7576(Boj7576bfs2), 11403(Boj11403floyd2)
* (29)추가 리스트 : 2665(Boj2665dij)
* (29)추가 리스트 : 2156(Boj2156dp2), 1915(Boj1915dp2)
* <11월> 
* (01)추가 리스트 : 11051(Boj11051dp),2362(Boj2362dp2),1012(Boj1012dfs2)
* (02)추가 리스트 : 1699(Boj1699dp2), 1238(Boj1238dij2)
* (03)추가 리스트 : 9095, 1463, 11726, 11727

2017.11.03 ** 금요일 ** Solution - 1463(1로만들기)

풀이방법: 동적계획법

DP를 풀 수 있다면 쉬운문데 ,

우리는 1로 만들것이고

문제에서는 이미 3개의 케이스를 줬다.

N의 케이스를 나눠보자

3으로 나누면 N의 상태는 N/3이된다.

2로 나누면 N/2

1을 빼면 N-1

이렇게 3개를 나눠서 최소값을 찾으면 되는 문제이다.

점화식 :

dp[1] = 0;

        for(int i = 2; i < N+1; i++) {

            dp[i] = dp[i-1] + 1;

            if(i%3==0&&dp[i] > dp[i/3]+1) {
                dp[i] = dp[i/3] + 1;
            }

            if(i%2==0&&dp[i]>dp[i/2]+1) {
                dp[i] = dp[i/2] + 1;
            }


        }

—————————————————————————————————————