[BOJ 백준] 1463번 - 1로 만들기

출처 : www.acmicpc.net/problem/1463

1463번: 1로 만들기

이전에 풀었던 문제중 하나였는데, 최근 재채점을 진행하였더니 오답처리 되었다. 그래서 다시 풀어보고 기록을 남긴다.

 

 

어떠한 정수가 주어질때 3가지 연산방법을 활용하여 1을 만들 수 있는 최소의 연산 횟수를 구하는 문제이다.

 

접근

정수 X가 1일 경우 : 바로 1이 만들어지므로 연산 횟수는 0이다.

 

정수 X가 2일 경우 : 2로 나누어 떨어지는 경우와 -1을 하는 경우 두가지가 있다.

2를 2로 나누어도 1이고 2에서 1을 빼도 결국 1이 나오는것은 같으므로 연산 횟수는 1이다.

 

정수 X가 3일 경우 : 3으로 나누어 떨어지는 경우와 -1을 하는 경우 두가지가 있다.

3을 3으로 나누면 1이고 3에서 -1을 하면 2 이다. 3으로 나눌때 1이 나오므로 최소 연산 횟수는 1이다.

 

정수 X가 4일 경우 : 2로 나누어 떨어지는 경우와 -1을 하는 경우 두가지가 있다.

4를 2로나누면 2이고, 2의 최소 연산횟수는 1이었으므로 2의 최소 연산횟수 + 1 (방금 2로 나눈 연산) 을 해준다.

-1을 하는 경우 3이 되고 3의 최소 연산횟수는 1이었으므로 3의 최소 연산횟수 +1 을 해준다.

결국 X가 4일때의 최소 연산횟수는 2이다.

 

정수 X가 5일 경우 : -1을 하는 경우만 있다. (5는 2 또는 3 으로 나누어떨어지지 않는다.)

5에서 -1을 하면 4이고 앞선 X가 4의 경우의 최소 연산횟수는 2였으므로,  2 + 1 (5에서 -1 연산) 을 하면

X가 5일때의 최소 연산횟수는 3이된다.

 

정수 X가 6일 경우 : 2로 나누어떨어지는 경우, 3으로 나누어떨어지는 경우, -1연산을 하는 경우 3가지가 모두 가능하다.

6을 2로 나눌경우 3이되고, 6을 3으로 나눌 경우 2가 되고, -1연산을 하게 되면 5가 된다.

여기서 6/2 -> 3의 경우와 6/3 -> 2 의 경우에서 최소 연산횟수는 둘다 1이었으므로 2로나누는 경우, 3으로 나누는경우의 연산 횟수는 2가 되고, -1 연산을 하는 경우에는 5가 되므로 5의 최소 연산횟수 + 1 을 하게되면 4가 된다.

이 3가지중 최소 연산횟수는 2이다.

 

종합해보면 다음과 같은 규칙성이 보인다.

 

정수 X가 2와 3의 약수가 아닐 경우 : -1의 연산만 고려하면 되므로 직전 숫자의 최소 연산횟수 + 1 이 곧 최소 연산횟수가 된다. 예를 들어, X가 17일 경우 17은 2와 3의 약수가 아니므로 x-1의 값인 16의 최소연산횟수 +1을 해주면 된다.

 

2의 약수이지만 3의 약수가 아님 : 2로 나누는 경우 , -1연산을 하는경우 두가지를 고려해야 한다.

예를 들어 X가 16일 경우 2의 약수이지만 3의 약수가 아니다. 16을 2로 나눈 값 8과 -1을 한 15 두가지가 있다.

8일때의 최소 연산횟수, 15일때의 최소 연산횟수 두가지 중 작은 값을 선택해서 +1을 하게 되면 X의 최소 연산횟수를 구할 수 있다. 즉, 2로 나눈 값의 최소 연산 횟수 와 -1을 한 값의 최소 연산횟수중 작은 값 + 1을 하면 된다.

 

3의 약수이지만 2의 약수가 아님 : 방금 2의 약수이지만 3의 약수가 아닌 경우의 반대로써, 3으로 나눈 값의 최소 연산 횟수와 -1을 한 값의 최소 연산횟수중 작은 값 + 1 하면 된다.

 

2의 약수이면서 3의 약수 : 2로 나눈 값과 3으로 나눈 값, -1로 나눈 값의 최소 연산 횟수 중 가장 작은 값 +1을 하면 된다.

 

 

 

코드 Github : github.com/devdinist/BOJ_Code

devdinist/BOJ_Code

 

C++

#include <stdio.h>
#include <algorithm>

using std::min;
int a[1000001];

int main(){
    
    int n,i;
    scanf("%d", &n);
    a[1] = 0;
    a[2] = 1;
    a[3] = 1;

    for(i = 4; i<=n; i++){
        if(i % 2 != 0 && i% 3 != 0){
            a[i] = a[i-1] + 1;
            continue;
        }
        if(i % 2 == 0 && i%3 != 0){
            a[i] = min(a[i/2],a[i-1]) + 1;
            continue;
        }
        if(i%2 != 0){
            a[i] = min(a[i/3],a[i-1]) + 1;
            continue;
        }
        if(i%2 == 0){
            a[i] = min(a[i/3],min(a[i/2],a[i-1])) + 1;
        }
    }

    printf("%d",a[n]);

    return 0;
}

 

JAVA

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] a = new int[1000001];
        a[1] = 0;
        a[2] = 1;
        a[3] = 1;
        for(int i=4; i<=n; i++){
            if(i%2 != 0 && i%3 != 0){
                a[i] = a[i-1] + 1;
                continue;
            }
            if(i%2 == 0 && i%3 != 0){
                a[i] = Math.min(a[i-1],a[i/2])+1;
                continue;
            }
            if(i%2 != 0){
                a[i] = Math.min(a[i-1],a[i/3])+1;
                continue;
            }
            a[i] = Math.min(a[i-1],Math.min(a[i/2],a[i/3]))+1;
        }
        System.out.print(a[n]);
    }
}