JArchive 프로그래밍 일기

문제

RGB거리 백준 1149번

리뷰

최소값을 구하는 문제이므로 DP로 문제를 풀었다. (최소, 최대, 경우의 수는 DP로 푼다)

이 문제는 '직전 값'과는 다른 색깔을 선택해야 한다는 것이 핵심이었다.

그래서 직전에 어떤 색을 칠했는지를 고려해서 현재 무슨 색을 선택할지 결정한다.

ex) 1을 칠했다면, 다음에는 2또는 3 중에서만 최소값을 골라야 한다.

역으로 생각하면, 현재 2를 칠한다면, 직전에는 1또는 3을 택했어야 한다.

배열 A에는 1행에서 R,G,B 값을 저장했다. 인덱스는 1,2,3 을 썼다.

배열 D에는 1행에서 마지막으로 R, G, B 값을 칠했을 경우의 최소값을 저장한다.

배열 A, D 둘다 0행이 아니라 1행부터 시작한다.

배열 D의 초기화는 배열 A의 1행의 값들로 초기화된다.

왜냐하면, 1번째 집에서 마지막으로 R값을 칠한 것의 최소값이 1번째 집의 R값이기 때문이다.

    // D 배열 인덱스도 1부터 시작. 
       D[1][1] = A[1][1];  // R을 마지막으로 칠한 경우. 
    D[1][2] = A[1][2];  // G를 마지막으로 칠한 경우. 
    D[1][3] = A[1][3];  // B를 마지막으로 칠한 경우. 

예를 들어, D[ 2 ] [ 2 ] 값을 구해보자.

D[ 2 ] [ 2 ] 는 2 번째 집을 G로 칠한 경우(2번째 색을 선택)의 최소값이다.

이것은 D[1] [1] 과 D[1] [3] 을 비교한 값에 A[2] [2] 를 더해서 구해진다.

1번째 집을 R값으로 칠한 경우의 최소값과 1번째 집을 B값으로 칠한 경우의 최소값 둘을 비교해서 최소값을 고른다. 그리고 현재 행 (2번째 집) A[2] [2 ] 값을 더한다.

따라서 점화식을 옮긴 코드는 아래와 같다.

      for(i = 2; i <= house; i++){ // 인덱스 2부터 시작

         D[i][1] = min(D[i-1][2], D[i-1][3]) + A[i][1]; // 현재 1를 택했다면, 직전에 2또는 3을 선택.
         D[i][2] = min(D[i-1][1], D[i-1][3]) + A[i][2]; // 현재 2를 택했다면, 직전에 1또는 3을 선택.
         D[i][3] = min(D[i-1][1], D[i-1][2]) + A[i][3]; // 현재 3을 택했다면, 직전에 1또는 2을 선택.
    }

코드

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

int A[1001][4];  // 3색 값 입력 받음  
int D[1001][4];

int main(void){

     int house, fir, se, th = 0;
     int i = 0;

    scanf("%d", &house);     

     for(i = 1; i <= house; i++){
         scanf("%d %d %d", &fir, &se, &th); 
         A[i][1] = fir;
         A[i][2] = se;
         A[i][3] = th;
    } // 입력받기 끝 

    // D 배열 인덱스도 1부터 시작. 
       D[1][1] = A[1][1];  // 1을 마지막으로 칠한 경우. 
    D[1][2] = A[1][2];  // 2를 마지막으로 칠한 경우. 
    D[1][3] = A[1][3];

      for(i = 2; i <= house; i++){ // 인덱스 2부터 시작

         D[i][1] = min(D[i-1][2], D[i-1][3]) + A[i][1]; // 현재 1를 택했다면, 직전에 2또는 3을 선택.
         D[i][2] = min(D[i-1][1], D[i-1][3]) + A[i][2]; // 현재 2를 택했다면, 직전에 1또는 3을 선택.
         D[i][3] = min(D[i-1][1], D[i-1][2]) + A[i][3]; // 현재 3을 택했다면, 직전에 1또는 2을 선택.
    }

    // 마지막 줄에는, 각각 마지막에 1또는 2또는 3을 칠한 경우의 최소값들이 들어있다.
    printf("%d", min( min(D[house][1], D[house][2]), D[house][3] )); 

    return 0;
}

문제

동물원 백준 1309번

리뷰

처음에는 왼쪽에 사자를 놓냐, 오른쪽에 놓냐만 생각하다가 점화식을 세우지 못했다.

구글링을 해보니까 [ 안 놓는다. 왼쪽칸에 놓는다. 오른쪽 칸에 놓는다. ] 세 가지로 생각한 포스팅이 있었고, 그제서야 이해가 됬다.

사자를 배치 안하는 것도 경우로 친다는 것을 유념해야하는 문제였다.

D[ N ] [ L ] 배열을 D[ 행 ] [ 열 ] 에 사자를 배치하는 경우의 수를 저장한다.

N = 1 일 때, 동물 우리는 1 * 2 칸이다.

1행 2칸이니까 사자를 배치하는 경우의 수는 [ 아예 안 놓는다. 왼쪽칸에 놓는다. 오른쪽 칸에 놓는다 ] 이렇게 3가지다.

따라서 D[1] [0] = 1 , D[1] [1] = 1 , D[1] [2] = 1

이것이 기본 값이다 (base case)

N = 2 일 때, 동물 우리는 2 * 2 칸이다.

D[2] [0] 에는 2행에 사자를 배치 안하는 경우다. 이 경우에는 1행에 사자를 배치 하든 말든 상관이 없다.

따라서 D[2] [0] = D[1] [0] + D[1] [1] + D[1] [2] = 3가지

D[2] [1] 에는 2행의 왼쪽칸에 사자를 배치하는 경우다. 이 때는 1행에 사자를 배치안하거나 1행 오른칸에 배치해야 한다.

따라서 D[2] [1] = D[1] [0] + D[1] [2] = 2가지

D[2] [2] 에는 2행의 오른쪽 칸에 사자를 배치하는 경우다. 이 때는 1행에 사자를 배치안하거나 1행 왼쪽칸에 배치해야 한다.

따라서 D[2] [2] = D[1] [0] + D[1] [1] = 2가지

그래서 아래의 점화식으로 정리할 수 있다. 값을 저장하기 전에 9901로 mod 연산을 해줘야 한다.

for(i = 2; i <= ca_size ; i++) { // 행 순회  
    D[i][0] = (D[i-1][0] + D[i-1][1] + D[i-1][2]) % MODNUM; 
    D[i][1] = (D[i-1][0] + D[i-1][2]) % MODNUM; 
    D[i][2] = (D[i-1][0] + D[i-1][1]) % MODNUM;  
}    

뭐지 .. 하면서 아리까리 했었고 혼자힘으로는 못했는데.

어렵지만 풀면서 재미있었다. 

다른 분들의 풀이를 검색해보니까, 더 간단한 점화식 풀이가 있었다.

N에 따라 경우의 수를 써보다가 규칙을 발견하셨나보다.

N   ans
1   3
2   7
3   17
4   41
dp[n] = dp[n-1]*2 + dp[n-2]

코드

#include <stdio.h>
#include <algorithm>
#define MODNUM 9901
using namespace std;

int D[100001][3];

int main(void){

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

     int ca_size = 0;
     int i = 0 ;

    scanf("%d", &ca_size);     

    // 0 사자 없음, 1 왼쪽칸에 배치, 2오른쪽칸에 배치. 

    D[1][0] = D[1][1] = D[1][2] = 1;  //     1 행의 경우,  

    for(i = 2; i <= ca_size ; i++) { // 행 순회  
        D[i][0] = (D[i-1][0] + D[i-1][1] + D[i-1][2]) % MODNUM; 
        D[i][1] = (D[i-1][0] + D[i-1][2]) % MODNUM; 
        D[i][2] = (D[i-1][0] + D[i-1][1]) % MODNUM;  
    }    

     printf("%d", (D[ca_size][0] + D[ca_size][1] + D[ca_size][2]) % MODNUM);

    return 0;
}

문제

1,2,3 더하기3 백준 15988번

리뷰

1,2,3더하기 문제와 똑같은데, 정수 n 의 크기제한과 출력의 조건을 주의해야 한다.

그래서 arr[i] 배열 자료형을 long long 으로 해줬고, 배열에 저장하기 전에 mod 연산을 해준다.

정수 i의 경우, 방법의 수를 D[i] 에 저장한다.

D[1] = 1

D[2] = 2

D[3] = 4

D[4] = 7

D[5] = 13

이렇게 되니까, 7 = 4 + 2 + 1 이었고, 13 = 7 + 4 + 2 였다.

[ 점화식 ]

D[i] = D[i-1] + D[i-2] + D[i-3]

코드

#include <stdio.h>
#define MODNUM 1000000009
using namespace std;

long long arr[1000000];

int sum_case(int num){

    int i = 0;

    for(i = 4; i <= num; i++){
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        arr[i] %= MODNUM;
    }

    return arr[num];
}

int main(void){

    int test_case = 0, num = 0;

    scanf("%d", &test_case);

    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;

    while(test_case--){
        scanf("%d", &num);
        printf("%d\n", sum_case(num));
    }

    return 0;
}

문제

가장 긴 증가하는 부분 수열 백준 11053번

리뷰

자신보다 작은 숫자의 개수를 세는 것이 핵심이다.

예시 배열 A = [10 , 20 , 10 , 30, 20 , 50] 이고 크기는 6이다.

입력 배열은 A[i] 에 인덱스 1부터 저장된다. 길이는 6이니까 A[1] ~ A[6] 까지 숫자가 저장되어 있다.

바깥 for문 i 를 기준으로 (자기자신 A[ 1 ] ) 자신보다 작은 숫자의 개수를 센다.

D[ i ] 배열에 A[ i ] 보다 작은 숫자의 개수를 저장한다.

D[i] 값은 안쪽 for문에 들어가기 전에 1로 초기화 된다. (자기 자신의 길이는 1이기 때문이다. )

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

        D[i] = 1; // 자기자신 길이 1 로 초기화 

        for(j = 0; j <= i; j++){
            if(A[i] > A[j]){
                D[i] = max(D[i], D[j] + 1);
            }
        }
        cnt = max(cnt, D[i]); // 여태 까지 구한 D 배열의 최대값을 기억한다. (답으로 출력)
    } 

예를 들어, i = 2 라면, A[2] 값 20 을 기준으로, A[0] , A[1] , A[2] 의 값을 비교한다.

A[2] > A[1] 인 경우에 if 문에 들어가게 된다. (현재 D[2] 값은 1이다. )

D[2] = max( D[ 2 ] , D[ 2 ] + 1)

​ = max ( 1, 2 )

D[2] = 2 이렇게 저장되고 끝나게 된다.

i = 3 이라면, A[3] 값 10을 기준으로 A[0] , A[1] , A[2] , A[3] 과 비교한다.

처음에 D[3] 값은 1이다.

그렇지만 10보다 작은 값이 없으니까 if문에 들어갈 일이 없다. if 문에 들어가지 못하고 종료된다.

A [ 4 ] 의 경우를 보자. A[4] 값 30을 기준으로 A[0] , A[1] , A[2] , A[3] , A[4 ] 값을 비교한다.

처음에 D[4] 값은 1이다.

if (30 > A[0]) 문을 만족한다. A[0] = 0이다.

D[4] = max ( D[4] , D[0] + 1) 이니까 D[4] = 1 이다.

if (30 > A[1]) 문을 만족한다. A[1] = 10 이다.

D[4] = max ( D[4] , D[1] + 1) 이니까 D[4] = 2 이다.

if (30 > A[2]) 문을 만족한다. A[2] = 20 이다.

D[4] = max ( D[4] , D[2] + 1) 이니까 D[4] = 3 이다.

if (30 > A[3]) 문을 만족한다. A[3] = 10 이다.

D[4] = max ( D[4] , D[3] + 1) == max ( 3 , 2 ) 이다.

따라서 D[4] = 3 그대로 유지된다.

if (30 > A[4]) 문을 만족하지 않는다.

D 배열을 전부 채운 결과

D 배열을 하나씩 채울 때 마다, 최대값을 cnt 변수에 기억한다.

최종 결과 4가 답으로 출력된다.

코드

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

int A[1001];
int D[1001];

int main(void){

     int len = 0, num = 0, cnt = 1;
    int i = 0, j = 0;

     scanf("%d", &len);

     for(i = 1; i <= len; i++){
         scanf("%d", &num);
         A[i] = num;
    } // 입력받기 끝 


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

        D[i] = 1; // 자기자신 길이 1 로 초기화 

        for(j = 0; j <= i; j++){
            if(A[i] > A[j]){
                D[i] = max(D[i], D[j] + 1);
            }
        }
        cnt = max(cnt, D[i]);
    } 

     printf("%d", cnt);

    return 0;
}

문제

합분해 백준 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;
}

문제

제곱수의 합 백준 1699번

리뷰

배열 D[i] 는 i를 제곱수의 합으로 표현했을 때 최소항의 개수를 저장한다.

기본적으로 D[i] 는 1의 제곱으로 i 개 더하면 i를 만들수 있다. D[i] = i

ex) D[1] = 1개, D[2] = 2개 ( 1^2 + 1^2 )

i를 제곱수로 표현할 때, 자신보다 작은 수의 제곱수들로만 구성되어 있다.

아래는 D[i] 의 최소항 개수를 1부터 5까지 구해본 것이다.

D[1] = 1개 ( 1^2)

D[2] = 1개 ( 2^2)

D[3] = 2개 ( 1^2 + 2^2)

D[4] =1개 ( 2^2 )

D[5] = 2개 ( 2^2 + 1^2 )

점화식은 다음과 같다.

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

    D[i] = i; // i를 1의 제곱의 합으로만 나타내면 항의 개수 i개  

    for(j = 1; j*j <= i; j++){  // i보다 작은 제곱수들 

        D[i] = min(D[i], D[i- j*j] + 1);

    }
}

n = 5로 주어질 때, D[5] 를 구해보자.

기본적으로 D[5] 는 1의 제곱의 합으로만 나타내서 5개의 항으로 구성할 수 있다. D[5] = 5개

5 보다 작은 제곱수는 1과 2가 있다.

그래서 i보다 작은 제곱수들(1 , 2 )의 합으로 i를 표현할 수 있다.

그래서 D[5] 는 D[2] 값에 1을 더한 경우, D[1의 제곱] 값에 1을 더한 경우 로도 나타낼 수 있다.

D[5] = D[2] + 1

D[5] = D[1] + 1

이 중에서 가장 작은 값이 D[5] 에 들어가야 한다.

D[5] = min ( 5, D[2] + 1, D[1] + 1 )

코드

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

// 1699번 제곱수의 합  

int D[100001]; 

int main(void){

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

    scanf("%d", &n);

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

        D[i] = i; // i를 1의 제곱의 합으로만 나타내면 항의 개수 i개  

        for(j = 1; j*j <= i; j++){  // i보다 작은 제곱수들 

            D[i] = min(D[i], D[i- j*j] + 1);

        }
    }

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

    return 0;
} 

문제

스티커 백준 9465번

리뷰

문제에 나와있는 그림 b 에서는

50, 50, 100, 60을 떼가야 260 최대 점수라는 예시 덕분에 풀 수 있었다.

지그재그로 떼는 경우 뿐만 아니라,

자기와 다른 행의 옆옆 스티커를 뗐을 때 최대값을 발견할 수도 있다는 것이다.

배열 S는 주어진 스티커 점수 배열이다.

배열 D를 D [행] [열] 이라고 하고, 해당 행과 열을 마지막으로 뗐을 때의 최대 스티커 점수를 저장한다.

하나의 열 마다 순회하는 for문을 만들고,

그 안에서 1행의 마지막일 경우의 최대값, 2행이 마지막일 경우의 최대값을 점화식으로 계산해서 D에 저장한다.

    //  D [행] [열]  
    D[1][i] = S[1][i] + max(D[2][i-1], D[2][i-2]);
    D[2][i] = S[2][i] + max(D[1][i-1], D[1][i-2]);

예를 들면,

D[1] [3] = 자기자신 S[2] [3] + max( D[2] [1] , D [2] [2] )

대각선으로 더했을 때 최대인지, 반대편 행의 옆옆 칸을 더했을 때 최대인지를 비교하면 된다.

코드

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

// 스티커 (BOJ 9465)

int S[3][100001]; // 입력받은 스티커 점수  
int D[3][100001];
int n, max_sum;

int Sticker(){

    // 1열 
    D[1][1] = S[1][1];
    D[2][1] = S[2][1];

    // 2열  
    D[1][2] = D[2][1] + S[1][2];
    D[2][2] = D[1][1] + S[2][2];

    for(int i = 3; i <= n; i++){

        D[1][i] = S[1][i] + max(D[2][i-1], D[2][i-2]);
        D[2][i] = S[2][i] + max(D[1][i-1], D[1][i-2]);
    }

    return max(D[1][n] , D[2][n]);
}

int main(void){

    int T = 0;
    int i = 0, num = 0;

    scanf("%d", &T);

    while(T--){

        scanf("%d", &n);

        for(i = 1; i <= n; i++){
            scanf("%d", &num);
            S[1][i] = num;
        }

        for(i = 1; i <= n; i++){
            scanf("%d", &num);
            S[2][i] = num;
        }

        printf("%d\n", Sticker());

    }

    return 0;
}