JArchive 프로그래밍 일기

문제

합분해 백준 2225번

리뷰

목표 합 n과 식의 개수 k를 관리하는 2차원 배열로 풀면 된다.

D[k] [n] 는 합이 n이 되는 k개의 항의 경우의 수를 저장한다.

D[2] [2] 는 합이 2가 되는 2개의 항의 경우의 수를 저장한다.

예를 들어, 0 + 2, 1 + 1, 2 + 0 이 있다. D[2] [2] = 3 이 저장된다.

목표합이 0 일 때, 항은 전부 0개 필요하다.

목표합이 1일 때, 항은 전부 그 숫자 1개가 필요하다. 따라서 아래와 같이 초기화 해준다.

     for(i = 0; i <= n; i++){   // 목표합이 i일 때, 항의 개수를 1개로 표현하면, 
        D[1][i] = 1; 
    }

2개의 항으로 3을 만드는 경우를 생각해보자.

k = 2, n = 3 이다.

0 + 3 -> 1개의 항으로 0이 되는 경우의 수 + 1개의 항으로 3이 되는 경우의 수

3+ 0 -> 1개의 항으로 3이 되는 경우의 수 + 1개의 항으로 0이 되는 경우의 수

2+ 1 -> 1개의 항으로 2이 되는 경우의 수 + 1개의 항으로 1이 되는 경우의 수

1+ 2 -> 1개의 항으로 1이 되는 경우의 수 + 1개의 항으로 2이 되는 경우의 수

이렇게 4가지 경우가 있으니까, D[2] [3] = 4 가 된다.

D[2] [3] = D[1] [0] + D[1] [1] + D[1] [2] + D[1] [3]

따라서 k=2 일 때, k-1 개의 항으로 0이 되는 경우의 수, 1이 되는 경우의 수, + ... n 이 되는 경우의 수를 더해야 한다.

D[k] [n] = D[k-1] [0] + D[k-1] [1] + ... + D[k-1] [n-1] + D[k-1] [n]

코드로 나타내면 3중 for문이 된다.

D[i] [j] 를 저장하기 전에 mod 연산이 필요하다는 것을 유의해야 한다.

    for(i = 2; i <= k; i++){ // 항의 개수 k  

        for(j = 0; j <= n; j++){  // 목표 합 n  

            for(s = 0; s <= j; s++){  // 0부터 목표 합까지 
                D[i][j] += D[i-1][s];
            }
            D[i][j] =  D[i][j] % MODNUM;
        }
    }

코드

#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

#define N_MAX 201
#define K_MAX 201
#define MODNUM 1000000000

// 2225  합분해  

long long D[N_MAX][K_MAX];  // MODNUM 으로 mod 연산 할꺼니까 long long형  

int main(void){

    int n, k = 0;
    int i, j, s = 0;

    scanf("%d %d", &n, &k); // 목표합, 항의 개수  

     for(i = 0; i <= n; i++){  // 목표합이 i 일 때, 1개 항으로 나타내는 경우의 수  
        D[1][i] = 1; 
    }

    for(i = 2; i <= k; i++){ // 항의 개수 k  

        for(j = 0; j <= n; j++){  // 목표 합 n  

            for(s = 0; s <= j; s++){ 

                D[i][j] += D[i-1][s];
            }

            D[i][j] =  D[i][j] % MODNUM;
        }
    }

    printf("%lld", D[k][n]); 

    return 0;
}

문제

카드 구매하기 백준 11052번

리뷰

유념해야 할 것은 카드 i개 들어있는 카드팩 가격이 P[i] 원 이라는 것이다.

점화식을 세우는 게 쉽지 않았다.

입력받은 카드팩 가격 배열 P[i]와 i장 샀을 때 최대값을 기억하는 배열 M[i]를 사용한다.

예제 입력 n = 4 , P[i] = [1, 5, 6, 7] 일 때, 예제 출력은 10이다.

카드 a 장을 살 때 최대 지불하는 금액을 배열 M[a] 에 넣고, 최종 답 M[n]을 구한다.

M[1] = max(P[1], M[1])

M[2] = max(M[1] + P[1] , M[2])

i = 5 인 경우,

M[1] + P[4], M[2] + P[3], M[3] + P[2] , M[4]+P[1] 인 경우를 비교해야 한다. -> 2중 for문

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

// 카드 구매하기  (BOJ 11052) 

vector<int> P(10001);
int max_value[1001];

int main(void){

    freopen("input.txt", "rt", stdin);

    int n = 0, num = 0;
    int i = 0, j = 0;

    scanf("%d", &n);

    for(i = 1; i <= n; i++){
        scanf("%d", &num);
        P[i] = num;
    } // 카드팩 n개의 값을 입력받는다. 

    for(i = 1; i <= n; i++){

        for(j = 1; j <= i; j++){ //   

            max_value[i] = max(max_value[i-j] + P[j], max_value[i]);

        }
    }

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

    return 0;
}