1로 만들기

이 문제는 다이나믹 프로그래밍 문제로, bottom-up 방식으로 문제를 해결하였습니다. 작은 값에서 부터 시작해서 큰 값으로 갈수록, 작은 값이었을 때 결과 값을 활용하는 방법입니다.

1. 입력 값 +1의 크기로 배열을 만든다.(시작값을 1로 하기 위해서, array0은 쓰지 않는다.)
2. 1일 때는 결과 값이 0이므로, array1에 0을 넣는다.
3. arrayi에 arrayi-1 + 1을 넣는다.
4. i가 2로 나누어 떨어지면, arrayi에 arrayi와 arrayi/2+1 중 작은 값을 넣는다.
5. i가 3으로 나누어 떨어지면, arrayi에 arrayi와 arrayi/3+1 중 작은 값을 넣는다.
6. 3-5번을 n까지 반복한다.
7. arrayn을 출력한다.

핵심코드는 다음과 같습니다.

for(int i = 1; i <= n; i++) {
    if(i == 1) {
        result[i] = 0;
    }else {
        result[i] = result[i-1] + 1;
        if(i%2 == 0) {
            result[i] = Math.min(result[i], result[i/2] + 1);
        }
        if(i%3 == 0) {
            result[i] = Math.min(result[i], result[i/3] + 1);
        }
    }
}
System.out.println(result[n]);

전체 소스 코드는 여기서 확인하실 수 있습니다.