문제

풀이
3개의 경우(3으로 나누어떨어짐, 2로 나누어떨어짐, 둘 다 아님) 중 어떤 경우에 어떤 연산을 고려해야 하는지 결정하는 것이 중요한 문제이다.
크게 4가지 케이스로 나눌 수 있다.
- 3과 2로 모두 나누어떨어질 때: 3으로 나누기/2로 나누기/1 빼기 中 연산 횟수 적은 것 택 1
- 3으로만 나누어떨어질 때: 3으로 나누기/1 빼기 中 연산 횟수 적은 것 택 1
- 2로만 나누어떨어질 때: 2로 나누기/1 빼기 中 연산 횟수 적은 것 택 1
- 1~3 중 해당사항 없을 때: 1 빼기
예제 2의 경우, N=10일 때 3번 케이스이므로, 2로 나누어 10→5→4 →2 →1로 진행할지(연산 횟수: 4) 1을 빼 10 →9 →3 →1(연산 횟수: 3)로 진행할 지 선택해야 한다.
if(arr[N]==null) {
if(N%6==0) {
arr[N]=Math.min(min(N-1), Math.min(min(N/3), min(N/2)))+1;
}
else if(N%3==0) {
arr[N]=Math.min(min(N/3), min(N-1))+1;
}
else if(N%2==0) {
arr[N]=Math.min(min(N/2), min(N-1))+1;
}
else {
arr[N]=min(N-1)+1;
}
return arr[N];
}
계산 효율을 위해 동적 계획법(dynamic programming)을 사용하였으며, 메모이제이션(memoization)을 위해 배열 arr은 Integer형 전역 변수로 선언하였다. 이 방법을 이용하면 arr[N]이 이미 정해진 경우 중복 연산을 하지 않으므로 시간을 단축할 수 있다.
비교 연산은 별도로 구현하지 않고 Math.min()을 사용하였다.
전체 코드
import java.util.Scanner;
public class Main {
static Integer[] arr;
public static int min(int N) {
if(arr[N]==null) {
if(N%6==0) {
arr[N]=Math.min(min(N-1), Math.min(min(N/3), min(N/2)))+1;
}
else if(N%3==0) {
arr[N]=Math.min(min(N/3), min(N-1))+1;
}
else if(N%2==0) {
arr[N]=Math.min(min(N/2), min(N-1))+1;
}
else {
arr[N]=min(N-1)+1;
}
}
return arr[N];
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int N=scanner.nextInt();
arr=new Integer[N+1];
arr[0]=arr[1]=0;
System.out.println(min(N));
}
}
입력이 1개라 Scanner를 사용했지만 BufferedReader 사용해도 무방하다.
'백준' 카테고리의 다른 글
백준 14244: 트리 만들기(java) (0) | 2024.08.20 |
---|---|
백준 9372: 상근이의 여행(java) (0) | 2024.08.19 |
백준 1874: 스택 수열(java) (0) | 2024.08.07 |
백준 5397: 키로거(java) (0) | 2024.08.07 |
백준 1302: 베스트셀러(java) (0) | 2024.08.07 |