[BOJ/백준 - 1463] 1로 만들기

문제 출처: https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

	public class BOJ_1463 {
	static int[] dp = new int[1000001];
	public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int targetN = Integer.parseInt(br.readLine());
	setDp();
	System.out.println(dp[targetN]);
	}
	static void setDp() {
	// 초기화값
	dp[2] = 1;
	dp[3] = 1;
	int case1; //3나누기
	int case2; //2나누기
	int case3; //1나누기
	for(int i=4; i<dp.length; i++ ) {
	case1 = Integer.MAX_VALUE;
	case2 = Integer.MAX_VALUE;
	case3 = Integer.MAX_VALUE;
	if(i%3==0) {
	case1 = dp[i/3];
	}
	if(i%2==0) {
	case2 = dp[i/2];
	}
	case3 = dp[i-1];
	dp[i] = Math.min(case3, Math.min(case1, case2)) + 1;
	}
	}
	}

view raw BOJ_1463.java hosted with ❤ by GitHub

---

 

DP 단계별 풀어보기 카테고리에 등록된 문제로 

DP 로 해결하자

 

일단 문제 예시 input인 10을 보자

이걸 10부터 찾아갈라는걸 공책에 손으로 해봐도 경우의 수가 좀 생기는 것을 알 수 있다

 

그럼 이걸 풀 때 input값에 어떤 연산을 하든 말든 상관없이 '최소한'의 연산을 하자는 것을 생각하자

 

이하 연산의 종류는 알파벳으로 그냥 적겠다

x: 3나누기 연산

y: 2나누기 연산

z: 1빼기 연산

 

그냥 직관적으로 떠올릴 수 있는 곳까지

1부터 차례대로 올라가면서 1로 가는 연산의 횟수를 적어보자

 

1은 아무 연산없으니까 0

2는 y -> 1

     z -> 1

     종류는 모르지만 1번의 연산을 통해 1로 만들 수 있다

3은 x -> 1

4는 y -> 2 -> y -> 1

     y -> 2 -> z -> 1

     z -> 3 -> x -> 1

     어떤 경로로 갈진 모르지만 2번의 연산이 필요하다

 

4를 보면 4에다가 y나 z 연산을 한번만 적용하면 2와 3으로 간다는 것을 알 수 있고

2와 3은 1로 가기 위한 최소 연산 횟수를 구해놓았기 때문에 

그 둘중에 더 작은값에 1을 더하면 4의 연산 횟수를 알 수 있다.