[백준 1463번] 1로 만들기 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

먼저 입력으로 주어진 N 값을 1로 만드는 데 필요한 최소한의 연산 횟수를 구하기 위해
1부터 N-1까지의 수를 1로 만드는 최소한의 연산 횟수가 필요하였습니다.

1은 1로 만드는 데 필요한 최소한의 연산 횟수는 0입니다.

2는 1로 만드는 데 필요한 최소한의 연산 횟수는 1입니다. (※2를 2로 나누면 1이 됨)

3은 1로 만드는 데 필요한 최소한의 연산 횟수는 1입니다. (※3을 3으로 나누면 1이 됨)

자 그럼 4의 경우는 어떠할까요? 4는 2로 나누어떨어지는 수입니다.

4를 2로 나누면 2가 되며 1번의 연산을 진행하였습니다.

이전 값에서 2는 최소한의 연산 횟수가 1이므로 4를 1로 만드는 최소한의 연산 횟수는 2가 됩니다.

그러나 4는 다른 방법으로 1로 만드는 경우도 존재합니다.

1을 빼고 3으로 나누면서도 최소한의 연산이 됩니다.

입력 수	연산1	결과1	연산2	결과2	연산횟수
4	÷2	2	÷2	1	2
4	-1	3	÷3	1	2

자 그럼 9의 경우는 어떨까요? 9는 3으로 나누어떨어지는 수입니다.

9를 3으로 나누면 3이 되며 1번의 연산을 진행하였습니다.

이전 계산 값에서 3은 최소한의 연산 횟수가 1이므로 9를 1로 만드는 최소한의 연산 횟수는 2가 됩니다.

입력 수	연산1	결과1	연산2	결과2	연산3	결과3	연산4	결과4	연산횟수
9	÷3	3	÷3	1	-	-	-	-	2
9	-1	8	÷2	4	÷2	2	÷2	1	4

그럼 2로 나누어떨어지거나 3으로 나누어떨어진다면 무조건 2또는 3으로 나누기를 먼저 하면 될까요?

10의 경우를 보면 2로 나눈다고 최소한의 연산 횟수가 나오지 않습니다.

입력 수	연산1	결과1	연산2	결과2	연산3	결과3	연산4	결과4	연산횟수
10	÷2	5	-1	4	÷2	2	÷2	1	4
10	-1	9	÷3	3	÷3	1	-	-	3

그럼 지금까지 수들의 계산을 보면 알 수 있듯이 2 또는 3으로 나누어떨어지는 수의 경우
1을 먼저 빼고 나온 수의 최소한의 연산횟수와 먼저 나누고 나온 수의 최소한의 연산횟수를 비교하여 작은 수가
최소한의 연산횟수가 됨을 알 수 있습니다.

즉 N이 2로 나누어떨어지는 경우 -> DP[N-1] + 1과 DP[N/2] + 1중 작은 값이 최소한의 연산 횟수가 되며
N이 3으로 나누어떨어지는 경우 -> DP[N-1] + 1과 DP[N/3] + 1중 작은 값이 최소한의 연산 횟수가 되며
2 또는 3으로 나누어떨어지지 않는 경우 -> DP[N-1] + 1이 됩니다.

마지막으로 추가되어야 하는 조건이 있습니다.

2와 3으로 동시에 나누어떨어지는 6의 배수인 경우 입니다.

이 경우 2로 나누어떨어지는 경우로 계산된 횟수와 3으로 나누어떨어지는 경우로 계산된 횟수 중 작은 수가 최소한의 연산 횟수가 됩니다.

6. 코드

전체 코드는 Git에 있습니다.

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

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

int[] dp = new int[1000001];

dp[2] = 1;
dp[3] = 1;

for(int i=4; i<=questionNum; i++){
	dp[i] = dp[i-1] + 1;

	int tmp3 = 0;
	int tmp2 = 0;

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

	if(tmp3 != 0 && tmp2 != 0)
		dp[i] = Math.min(tmp3, tmp2);
}

bw.write(dp[questionNum] + "\n");
bw.flush();