BOJ 백준 1463, 11726, 11727, 9095

DP는 점화식을 만들어 내는것이 중요하다.

01. 1463번 - 1로만들기

숫자 N이 주어질때, N이 3으로 나눠지면 나누고, 다음 2 다음 -1 해보는 방법을 생각해볼 수 있다.( 그리디 ) 그러나 이 방법으로 문제를 풀게 되면, N=10일때 문제를 풀 수 없다. 

위 방법으로는 10->5->4->2->1 이렇게 4번의 계산이 필요하다. 그러나 정답은 10->9->3->1 로 3번의 계산으로 풀수있다.

이렇다면 배열 d[N] = "N을 1로 만드는데 드는 최소의 연산횟수"  라고 정의하자.

문제의 방법에도 나와있듯 연산하는 방법은 총 3가지이다.

1. N/3 : 맨처음 N를 N/3했다면 1번의 계산을 한것이다. 그럼 나머지 N/3 숫자부터~~~~ 1까지에는 연산이 몇번 필요할까? d[N]을 N을 1로만드는 최소 연산횟수라 하였으니, N/3을 1로만드는 최소 연산횟수는 d[N/3]일것이다. 따라서 N을 N/3을 사용하여 1로만드는 방법은 총 d[N/3] +1 ( N/3 계산 한번해줌 ) 번의 경우의 수가 된다. 

2. N/2 : N/2도 N/3과 마찬가지로 d[N/2] +1 번의 경우의 수가 된다. : 

3. N-1 : 마찬가지로 d[N-1]+1 번의 경우의수이다.

d[N]을 구할수 있는 경우의 수가 총 위의 3가지 방법이 있으니, 최소를 고른다면 d[N] =  min(d[N/3], d[N/2], d[N-1]) +1 일것이다. 이렇게 점화식을 구할 수 있다.

#include <iostream>
#include <vector>
using namespace std;

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin>>N;
    vector<int> d(N+1);
    
    d[1] = 0; //연산 사용하지 않음
    
    for(int i=2; i<=N; i++){ //bottom-up
        d[i] = d[i-1] +1;
        if(i%2==0 && d[i/2]+1< d[i]){
            d[i] = d[i/2] +1;
        }
        if(i%3==0 && d[i/3]+1 < d[i]){
            d[i] = d[i/3]+1;
        }
    }
    
    cout<<d[N];
    
    return 0;
}

 

02. 11726번 - 2xN 타일링

2xN이 주어질때, 마지막 타일을 놓는 경우를 생각해보자. 마지막 타일을 놓는 경우는 두가지가 있다.

2x1타일을 하나 놓거나, 1x2 타일을 두가지 놓는 경우이다. 그렇다면 D[n]을 구하는방법은 2가지가 있는것이다.

D[n] = D[n-1] + D[n-2] 이다. 2x1 타일을 하나빼면, 나머지 채워야하는 n은 n-1이된다. 1x2 타일을 두개 빼면 나머지 채워야하는 n은 n-2가 된다.

#include <iostream>
using namespace std;
int d[1001];

int main()
{
    int n;
    cin>>n;
    
    d[1]=1;
    d[2]=2;
    d[3]=3;
    
    for(int i=4; i<=n; i++){
        d[i] = ((d[i-1]%10007)+(d[i-2]%10007))%10007;
    }
    
    cout<<d[n];
    
    return 0;
}

 

03. 11727번 - 2xN 타일링2

이 문제는 타일의 종류가 하나 더 늘어났다. 2x2의 타일이 하나 더 늘어났다. 때문에, d[N-2]가 하나 더 추가된격이다.

점화식은 이렇게 된다. D[n] = D[n-1] + D[n-2]*2

 

04. 9095번 - 1, 2, 3 더하기

D[n] = n을 1,2,3의 합으로 나타내는 방법의 수 라고정의할때

ㅇ + ㅇ+ ㅇ+ ㅇ+ ㅇ+ .... + ㅇ = n 이라고 가정할때, 마지막 ㅇ가 될수있는 경우의 수를 찾아보자.

아래와 같이 3가지의 경우가 있을 것이다.

ㅇ 가 1일때 : ㅇ+ㅇ+ㅇ+ㅇ+...+1 = n 이라면 앞의 ㅇㅇㅇ들은 n-1이 될것이다. 따라서 D[n-1] 은 마지막 1을 제외한 숫자를 1,2,3의 합으로 나타내는 방법의 수 일것이다.

ㅇ 가 2일때 : 마찬가지로 ㅇㅇㅇ들은  n-2가 된다. 

ㅇ 가 3일때 : n-3이된다.

이렇게 총 d[n-1] d[n-2] d[n-3] 의 방법의 수에 각각 한가지의 경우 +1 +2 +3 이므로, 3가지 경우를 모두 합한것이 d[n]의 값이 된다.

d[n] = d[n-1]+d[n-2]+d[n-3]

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    int n;
    cin>>T;
    
    for(int i=0; i<T; i++){
        
        cin>>n;
        vector<int> d(n+1);
        
        d[0] = 1; d[1] =1; d[2] =2;
        for(int j=3; j<=n; j++){
            
            d[j] = d[j-1]+d[j-2]+d[j-3];
            
        }
        
        cout<<d[n]<<'\n';
    }
    
    return 0;
}

 

모두 bottom-up방식으로 풀었다.