문제
해결 방안 고민
•
해당 문제는 DP 문제로서 다음 3가지를 생각해야 한다.
◦
테이블 정의
◦
점화식 찾기
◦
초기값 정하기
•
솔직히 초기값, 점화식 다 고려하는 게 쉽지않았다.
•
그나마 1부터 12까지 1로 만들 수 있는 경우의 수를 확인했을 뿐이다.
◦
그 경우의 수가 힌트였는데 그것을 제대로 파악하지 못했다.
// 1로 만들기 - 실버 3
// 정수 X에 사용할 수 있는 연산 3가지
/*
* 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
* 2. X가 2로 나누어 떨어지면, 2로 나눈다.
* 3. 1을 뺀다.
*/
// 위와 같은 연산 3개를 사용, 1을 만들어야 한다. 연산을 사용하는 횟수의 최솟값 출력하기.
// 10 입력 -> /2 -> 5 -> /2, /3 -> 5 - 1 = 4 -> 4 / 2 = 2 / 2 = 1
1 1 1 2 3 2 3 3 2 3 4 3
/*
1 => 1
2 => 2 / 2 => 1
3 => 3 / 3 => 1
4 => 4 / 2, 2 / 2 => 2
5 => 5 - 1, 4 / 2, 2 / 2 => 3
6 => 6 / 2, 3 / 3 => 2
7 => 7 - 1, 6 / 2, 3 / 3 => 3
8 => 8 / 2, 4 / 2, 2 / 2 => 3
9 => 9 / 3, 3 / 3 => 2
10 => 10 - 1, 9 / 3, 3 / 3 => 3
11 => 11 - 1, 10 - 1, 9 / 3, 3 / 3 => 4
12 => 12 / 2, 6 / 2, 3 / 3 => 3
12 => 12 / 3, 4 / 2, 2 / 2 => 3
*/
Java
복사
해결 방법
•
결국 다른 블로그를 참고하여 문제를 해결했다.
•
점화식을 정리하자면 다음과 같다.
◦
dp[12]가 있다고 하면
◦
3으로 나누었을 때 (dp[12] = dp[4] + 1) = (dp[i] = dp[i / 3] + 1)
◦
2로 나누었을 때 (dp[12] = dp[6] + 1) = (dp[i] = dp[i / 2] + 1)
◦
1을 뺐을 때 (dp[12] = dp[11] + 1) = (dp[i] = dp[i - 1] + 1)
⇒ 결국 dp[12] ⇒ min(dp[4] + 1, dp[6] + 1 , dp[11] + 1)
⇒ dp[i] = min(dp[i / 3] + 1, dp[i / 2] + 1, dp[i - 1] + 1)
•
0과 1은 고려하지 않기에 dp[0], dp[1]은 0으로 정한다.
코드
import java.io.*;
// 1로 만들기 - 실버 3
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] dp = new int[N + 1]; // 배열 요소는 0부터 시작함을 고려
dp[0] = 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);
}
}
bw.write(String.valueOf(dp[N]));
bw.flush();
bw.close();
br.close();
}
}
Java
복사
확인 결과
느낀 점
다이나믹 프로그래밍은 다른 알고리즘과 비교했을 때 생각보다 직관과 규칙을 필요로 하는 문제들이 많다. 그러다 보니 풀이방법이 잘 떠오르지 않거나 아예 손도 댈 수 없는 문제들이 많다. 문제를 풀다 보면 일반화할 수 있는 규칙들이 보이는데 이 부분을 찾아내기가 쉽지 않다. 찾았다고 해서 그것을 곧바로 코드로 적용하기도 어렵다. 결국 경험을 통해 규칙을 코드로 작성할 수 있는 역량을 지속적으로 쌓는 게 중요하지 않을까 싶다.