[JAVA] 백준 1463번

1463번 - 1로 만들기

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int[] dp;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int X = Integer.parseInt(br.readLine());

		dp = new int[X + 1];

		dp[0] = dp[1] = 0;

		for (int i = 2; i <= X; i++) {

			if (i % 6 == 0) {
				dp[i] = Math.min(Math.min(dp[i / 3], dp[i / 2]), dp[i - 1]) + 1;
			} else if (i % 3 == 0) {
				dp[i] = Math.min(dp[i / 3], dp[i - 1]) + 1;
			} else if (i % 2 == 0) {
				dp[i] = Math.min(dp[i / 2], dp[i - 1]) + 1;
			} else {
				dp[i] = dp[i - 1] + 1;
			}

		}

		bw.write(String.valueOf(dp[X]));

		bw.flush();
		bw.close();

	}

}

 

동적계획법, 다이나믹프로그래밍(DP) 첫 문제이다.

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법으로 개념은 알고 있었지만 실제 코드로 구현하기 너무 어려웠다. 메모이제이션 방법을 활용해서 정답을 맞추었다.

 

 

처음 문제에 접근한 방식

1. X의 값을 가장 큰 수로 나누었을때 가장 작아지기 때문에 X/3, X/2, X-1 순서대로 조건문을 만들어 계산함

2. 10의 경우 예외적으로 10 -> 9 -> 3 -> 1로 3번만에 값을 얻을 수 있어 10의 배수로 나눌경우의 조건도 추가함

3. 결론은 오답

 

정답을 맞춘 풀이방법

1 . Bottom - Up 방식을 활용하여 X값을 1로 만들기 위해 각각의 DP값을 저장할 배열을 선언함.

2.  6의 배수의 경우 i/3, i/2, i-1 값중 최소계산횟수값 + 1의 값을 현재구하는 dp[i]값에 저장

3.  최종적으로 구하고자하는 dp[x]의 값을 출력함