[BOJ_1463/JAVA] 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제

풀이

해당 문제는 다이나믹 프로그래밍 문제이다. 

다이나믹 프로그래밍이란 큰 문제를 작은 문제로 나누어 푸는 문제를 말한다. 

 

1. 3을 나누었을 때

2. 2을 나누었을 때

3. -1을 해주었을 때

이 세가지 케이스를 진행한 다음에 최솟값을 저장해주는 식이다.

 

dp배열을 만들어준 다음에, 안에 들어가는 값은 횟수의 최솟값이다.

0하고 1은 0이니 처음부터 dp[0] = dp[1]=0 으로 값을 넣어주자.

그리고 2부터 N까지 반복하면서 배열 안에 값을 넣어준다.

 

i=2일 때, 3번 케이스의 경우

dp[2]=dp[1]+1;

2에서 -1을 해준 값인 1 인덱스값과 +1 을 해준다.

+1를 해주는 이유는 -1을 해주는 것도 연산을 하는 것이기에 +1 을 해준다.

 

i=2일때, 2번 케이스인 경우

if(2%2==0) dp[2]=Math.min(dp[2], dp[2/2]+1);

 앞서 -1 해준 값과 2로 나누었을 때 값을 비교해서 둘 중 최솟값을 dp[2]에 저장해준다.

 

i=2일때, 3번 케이스인 경우는 if문에 못들어가니 패스한다.

 

i=3일때도 반복하고 .... N까지 반복하면 배열 안에 값이 최솟값이 다 들어갈 것이다.

 

만약, N이 6이라면 2도 나눠지고 3도 나눠질 것이다. 그러면 처음에 -1한 값과 2로 나눈값의 최솟값을 dp[6]에 저장하고,

그리고 다시 두번째 if문에 들어가 앞서 저장한 최솟값(dp[6])과 3으로 나눈 값을 비교해서 더 작은 값을 dp[6]에 재저장한다.

 

그 다음에 dp[N] 값을 출력하면 된다.

 

코드

package Week06;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ1463 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int [] dp = new int[n+1];
		
		dp[0]=dp[1]=0;
		
		for(int i=2;i<=n;i++) {
			dp[i]=dp[i-1]+1;
			
			if(i%2==0) dp[i]=Math.min(dp[i], dp[i/2]+1);
			if(i%3==0) dp[i]=Math.min(dp[i], dp[i/3]+1);
			
		}
		
		System.out.println(dp[n]);
		
		

	}

}

---

다이나믹 프로그래밍은 처음이라 아직도 어렵게 느껴진다. 이것이 다이나믹 프로그래밍의 제일 쉬운 문제라는데 큰일났다 ..