backjoon - 1463 번 [ 1로 만들기 ]

링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제는 다음과 같다.

 

 

흠 우선 문제 조건에서 보듯이 사용할 수 있는 연산은 

X%2가 0일 때 X/2, X%3가 0일때 X/3 일때 그리고 X-1이 있다. 

 

이 문제를 풀기 위해서 접근하는 방식은 배열의 크기가 10의 6승만큼 주어지고, 정수 X가 주어지면(X>1일 때, 1은 그냥 몇 번만에

구할 것도 없이 자체 1 이니깐 0)  두 번째 index부터 시작해서(기본의 배열의 0번째 인덱스를 첫 번째 인덱스라고 가정)에서 부터 시

작하여 위에 연산 3개를 활용하여 각각 현재 index i%3==0이 성립할 경우 i/3을 한값과 i%2==0 이 성립할 경우 i/2를 한 값,

i-1을 한 값을 구하여 3개의 index 중 가장 index내부 원소가 적은 값+1을 현재 index의 값에 넣어주고, 다음 index에서도 이전 인덱스

의 과정과 마찬가지로 현재 index에다가 i/2, i/3 , i-1번째 인덱스 안의 값 중 가장 작은 것을 찾아 +1  한 값을 넣어주어서 X까지 반복

하여 X에서 1까지의 최소 연산 값을 구하면 된다.

 

예를 들어 X가 5로 주어졌을 때의 경우를 살펴보자.

 

 

0

0

0

0

0

 

 

처음에 모든 원소들이 0으로 초기화된 배열이 있을 때, 아까도 말했듯이 1은 더이상 연산을 안하니깐 0으로 두고 두 번째 index 에다가 

2에서 1로 만들 수 있는 최소 연산 횟수를 구해 보장 2는 2%3==0이 아니므로 2/3 연산은 못하지만, 2-1 연산과 2/2 연산을 수행할 수가 

있다. 여기서 두 개의 연산 결과 둘 다 2-1=1이고 2/2=1이므로 1번째 index의 원소 +1 한 값을 2번째 index 의 원소에다가 대입해주면

된다. 그러면 2는 한 번의 연산만에 1을 구할 수 있음을 알 수 있다.

 

 

0

1

0

0

0

 

 

위의 과정을 거치게 되면 배열 내부의 원소들은 다음과 같이 됨을 확인할 수가 있다.

 

이제 다음으로 3에서 1로 만들 수 있는 최소 연산 횟수를 구해보도록 하자 3으로 할 수 있는 연산은 3%2=0 이 아니므로 3%3과

3-1 연산 두 가지가 있다. 즉 1 번째 index와 2번째 인덱스 중 원소 값이 더 적은 첫 번째 index+1 한 값을 3번째 index에다가 넣어 주

면 된다 흠 이쯤에서 알 수 있는 것은 2나 3이나 1로 만들기 위해 단 1번의 연산만 돌리면 구할 수 있다는 것이다. 왜냐하면 2도

-1이나 /2를 하면 1로 만들 수 있고 3도 /3을 하면 1로 만들 수 있기 때문이다. 그리고 위 조건의 연산들을 돌려 구한 값들 중 

가장 작은 원소+1을 한 이유는 3의 경우처럼 3/3을 하여 나온 1 즉, 1번째 index 원소+1을 하면 1이므로 즉 1번 만에 구할 수 있는데, 만약

3-1을 하고 나온 2로 한 번도 연산을 하여 1을 구하게 되면 두 번 연산을 하게 되기 때문이다.

 

 

0

1

1

0

0

 

 

다음과 같은 두 번의 과정을 거치면 배열 원소들이 다음과 같이 변했음을 확인할 수 있다.

이제 4에서 1로 구할 수 있는 최소 연산 횟수를 구해보자 4는 /2와 -1이 가능하므로 4/2=2와 4-1=3이 나온다. 그러므로

2번째 인덱스 원소와 3번째 인덱스 원소중 작은 것을 찾아야 하는데 둘 다 1이므로 그냥 1+1한 값을 4 번째 인덱스에 넣어

주면 된다. 4에서 1로 만들 수 있는 경우를 생각해보면 4/2한 값 2에다가 -1을 하거나 /2를 하여 1을 만들어도 두 번의 연산과

정을 거치게 되고 4-1한 3에다가 /3을 하여도 최 소 두 번의 연산 과정을 거치게 됨을 알 수 있다.

 

 

0

1

1

2

0

 

여기까지가 4에서 1을 구하는 최소 연산을 한 후의 배열 모습이다. 이제 마지막으로 5에서 1을 구하는 최소의 연산 횟수를

구해보면 5는 %2도 %3도 0으로 안 나누어 떨어지므로 할 수 있는 연산은 i-1 연산 밖에 없다. 즉, 현재 index 5-1한 4 index

의 원소인 2+1을 하여 5번째 index의 원소에 집어 넘으로써 우리는 5에서 1을 구하는데 3번의 연산을 하면 됨을 알 수가 있다.

 

 

 

#include <iostream>
#include <climits>
 
using namespace std;
 
int main() {
    
    int N=0;
    int min=INT_MAX;
    int min_idx=0;
    int arr[1000001]={0,};
    
    cin >> N;
    
    for(int i=2;i<=N;i++){
        if(arr[i-1]<min){
            min=arr[i-1];
            min_idx=i-1;
            
        }
        if(i%2==0 && arr[i/2]<min){
            min=arr[i/2];
            min_idx=i/2;
            
        }
        if(i%3==0 && arr[i/3]<min){
            min=arr[i/3];
            min_idx=i/3;
            
        }
        arr[i]=arr[min_idx]+1;
        min=INT_MAX;
 
    }
    
    cout << arr[N] << endl;
    
    return 0;
}

 

 

위 코드와 같이 큰 문제를 작은 문제로 나누어서 푸는 방법을 다이나믹 프로그래밍(Dynamic programming)이라고 한다.

그중에서도 이 문제는 작은 문제들 부터 하나하나 풀어가는 bottom-up 다이나믹 프로그래밍 방식으로 풀었다.