백준 자바 1463 1로만들기

이번 주제는 다이나믹프로그래밍, 즉 DP에 관한 내용이였다.
이런 스타일의 문제들은 예전에 싸피를 살짝 준비하면서
접한 경험이 있어, 재미있게 풀었던 것 같다.

우선, 이번 문제는 정수 x가 3의 배수면 3으로 나누고,
2의 배수면 2로 나누고 두 경우에 해당 되지않으면 1을 뺀다.
이 과정을 반복하여 1을 만드는 최솟값을 구하는 문제이다.

예를들어, x가 12이라면 D[12] 라고 했을 때,
D[12]의 값은 min( D[6]+1 , D[4] +1, D[11] +1 )이다.
이런식으로 반복하여 D[1]~ D[12]까지의 각각의 최솟값들 체크하여 활용하는 문제이고, 초기 값으로 D[1]은 아무런 변화가 없으므로 0을 지정하여 문제를 진행하였다.

package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Ox13_Q1_1 {
	// 백준 1463 S3 
		public static void main(String [] args) throws IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int n = Integer.parseInt(br.readLine());
			
			int cnt = 0;
			int [] arr = new int [n+1];
			
			// 초기 배열 값 세팅
			arr[1] = 0;
			
			for(int i =2; i<=n; i++) {
				arr[i] = arr[i-1]+1;
				if(i%2 == 0) {arr[i] = Math.min(arr[i], arr[i/2]+1);}
				if(i%3 == 0) {arr[i] = Math.min(arr[i], arr[i/3]+1);}
			}
			System.out.println(arr[n]);
		}
}

i = 1 에 해당되는 arr[1]은 기본적으로 0을 세팅해뒀으므로, 반복문은 2부터 n까지 진행한다.
다음으로 arr[i] 에 기본적으로 arr[i-1]+1 을 지정하고,
이 값과 arr[i/2]+1, arr[i/3]+1 을 각각의 경우에 맞게 비교하여
더 작은 값을 지정해주었다. 마지막으로, arr[n]의 값을 호출하면서 마무리했다.

아무래도 감을 익히는 문제이기에 수월하게 해결하였다.

굿