백준 1463번: 1로 만들기, 세 연산의 횟수 비교하기
나눌 수 있다고 먼저 나누지는 않습니다
백준 1463번은 정수 N에 연산을 적용해 1을 만들 때, 그 최소 횟수를 구하는 문제입니다. 3으로 나누어떨어지면 3으로 나누고 2로 나누어떨어지면 2로 나눌 수 있습니다. 1을 빼는 연산도 사용할 수 있습니다.
10에서 2로 나누기부터 시작하면 10 → 5 → 4 → 2 → 1로 네 번이 필요하지만 1을 먼저 빼면 10 → 9 → 3 → 1로 세 번에 끝납니다. 나눗셈을 먼저 선택한다고 항상 횟수가 줄어들지는 않습니다.
작은 수의 답을 저장합니다
arr[i]에는 i를 1로 만드는 최소 연산 횟수가 들어갑니다. 배열의 초기값은 0이고 이미 1인 경우에는 연산이 필요 없으므로 arr[1]도 0입니다. 입력 범위에 포함된 N = 1에서는 그대로 0을 출력합니다. 계산은 2부터 시작합니다.
먼저 arr[i - 1] + 1을 넣습니다. i에서 1을 빼는 데 한 번, 그 뒤에는 이미 구해 둔 횟수만큼 연산한다는 뜻입니다. 2나 3으로 나눌 수 있다면 그 경로의 횟수와도 견줘 봅니다.
2에서는 1을 빼거나 2로 나누는 두 경로 모두 한 번입니다.
3에서는 arr[2] + 1과 arr[1] + 1 중 작은 쪽을 고릅니다. 코드의 Math.min(arr[i], arr[i / 3] + 1)이 이 비교를 맡습니다.
6은 2와 3으로 모두 나눌 수 있으므로 세 경로를 전부 비교합니다. 이 과정을 반복하면 10에서는 arr[9] + 1이 최솟값이 됩니다.
제출 코드
import java.io.*;
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[] arr = new int[N + 1];
//arr[0] = 0;
//arr[1] = 0
// 점화식은 i=2 부터 시작
for (int i = 2; i < N + 1; i++) {
arr[i] = arr[i - 1] + 1;
if (i % 2 == 0) arr[i] = Math.min(arr[i], arr[i / 2] + 1);
if (i % 3 == 0) arr[i] = Math.min(arr[i], arr[i / 3] + 1);
}
bw.write(String.valueOf(arr[N]));
bw.flush();
}
}