- Today
- Total
개발하는 고라니
[백준] 1463번 : 1로 만들기 본문
# 문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
# 입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
# 출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
# 예시 입력
10
# 예시 출력
3
비교적 접근하기 쉬운 문제였다. 동적 프로그래밍 문제이며 1부터 주어진 수 x까지 loop를 돌며 각 숫자를 문제에 제시된 조건 연산을 따르며 1로 만드는 경우의 수 중 최소값을 찾는 문제이다. 숫자 n이 1로 될 수 있는 최소 경우의 수를 arr[] 배열에 담는다.
예를 들어 1을 1로 만들 수 있는 최소 경우의 수는 0이다. 이미 자체로 1이므로 즉 arr[1] = 0
2는 2로 나누어 떨어지므로 2 / 2 = 1 즉 arr[2] = 1
3도 마찬가지로 3으로 나누어 떨어지므로 3 / 3 = 1, arr[3] = 1
4는 2로 나누어 떨어지므로 4 / 2 = 2, 2 / 2 = 1 그리고 4 - 1 = 3, 3 / 3 = 1 이다. 어쨋든 arr[4] = 2
이쯤 했으면 전체 경우의 수를 찾아 나서는 일은 비효율적임이 분명하다. 내가 생각한 가장 최적의 알고리즘은 다음과 같다.
arr[1] -> 1
arr[2] -> 1
arr[3] -> 1
for i=4 -> x then { //x는 주어진 수, 단 1 <= x <= 1,000,000
temp = 999999
if i % 3 == 0? then //case 1
temp = Math.min(temp, arr[i/3] + 1)
if i % 2 == 0? then //case 2
temp = Math.min(temp, arr[i/2] + 1)
temp = Math.min(temp, arr[i-1] + 1) //case 3 (default)
arr[i] = temp
}
return arr[i]
숫자 i에 대해 3가지 케이스를 조건 검사한다.
1) 3으로 나누어 떨어지는가?
2) 2로 나누어 떨어지는가?
3) 조건에 관계 없이 실행
temp를 왠만해서 도달할 수 없는 큰 수로 지정해놓고, Math.min()으로 점점 더 작은 값을 찾아 나서는 작업이다.
# Whole Code </> - Java 11
public class Main {
static int getMinCnt(int x) {
int[] arr = new int[x+1];
int temp;
arr[1] = 0;
if(x >= 2) arr[2] = 1;
if(x >= 3) arr[3] = 1;
if(x >= 4)
for(int i=4; i<=x; i++) {
temp = 999999;
if(i % 3 == 0){
temp = Math.min(arr[i/3] + 1, temp);
System.out.printf("case 1: arr[%d] = %d\n", i, temp);
}
if(i % 2 == 0){
temp = Math.min(arr[i/2] + 1, temp);
System.out.printf("case 2: arr[%d] = %d\n", i, temp);
}
temp = Math.min(arr[i-1] + 1, temp);
System.out.printf("case 3: arr[%d] = %d\n", i, temp);
arr[i] = temp;
}
return arr[x];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
if(x < 1 || x > 1000000) System.exit(0);
System.out.printf("%d\n", getMinCnt(x));
}
}
'Programming > 백준' 카테고리의 다른 글
[백준] 2156번 : 포도주 시식 (0) | 2021.01.16 |
---|---|
[백준] 10844번 : 쉬운 계단 수 (0) | 2021.01.15 |
[백준] 2579번 : 계단 오르기 (0) | 2021.01.14 |
[백준] 1149번 : RGB거리 (0) | 2021.01.13 |
[백준] 9184번 : 신나는 함수 실행 (0) | 2021.01.11 |