JArchive 프로그래밍 일기

문제

계단 오르기 백준 2579번

리뷰

점화식을 구하는 데 조금 헤맸다.

계단이 1, 2, 3, 4번이 있고, 만약 현재 4번째 계단에 위치한다면,

max(2번째 계단까지의 최대값 + 4번째 계단점수 , 3번째 계단까지의 최대값 + 4번째 계단점수)

이렇게 비교해서 4번째 계단까지의 최대값을 구할 수 있을 줄 알았는데, 틀렸다.

이유는 4번이 마지막 계단(반드시 밟아야 하는 계단) 이라면,

2번을 밟고 4번을 밟았는지, 1번, 3번을 밟고 4번을 밟았는지를 비교해야 했다.

(OXOO or OOXO )

3번을 밟은 경우에는, 반드시 1번을 밟고 온 경우만 고려해야 한다. (왜냐하면 1, 2, 3 연속으로 밟으면 안되기 때문이다. )

case1) 1번 계단까지의 최대값 + 3번 계단점수 + 4번 계단점수

case2) 2번 계단까지의 최대값 + 4번 계단점수

이 두 가지의 경우를 비교하면서 DP로 푼다.

// i : 도착 계단 (반드시 밟아야함)

    case1 = D[i-3] + S[i-1] + S[i]; 
    case2 = D[i-2] + S[i];

코드

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

int S[301]; // i번 계단의 점수 
int D[301]; // i번 계단까지의 최대점수 기록 

int Max(int stair_size){

    int i = 0;
    int case1, case2 = 0;

    for(i=3; i<= stair_size; i++){

        case1 = D[i-3] + S[i-1] + S[i];
        case2 = D[i-2] + S[i];

        D[i] = max(case1, case2);

    }

    return D[stair_size];
}

int main(void){

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

    int stair_size, i = 0, num = 0;

    scanf("%d", &stair_size);

    for(i = 1; i <= stair_size; i++){
        scanf("%d", &num);
        S[i] = num; // 계단의 점수 입력받음 
    }

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

    printf("%d", Max(stair_size));

    return 0;
}

문제

1,2,3 더하기5 백준 15990번

리뷰

n을 1,2,3의 합으로 나타내는 경우의 수를 구해봤을 때, 규칙이 있는지 정수 8까지 경우를 써봤다.

정수 n이 3의 배수인 경우에는 이전 합에서 * 2를 하면 되는줄 알았는데, 점화식이 틀렸다.

다른 분 풀이를 보니까 n을 때, 마지막 수가 i인 경우를 따져봤다. (i는 1, 2, 3 )

연속으로 같은 숫자를 쓸 수 없음을 이용한 것이다.

정수 n 이 주어지면, 마지막 수가 i인 경우 (i는 1, 2, 3 ) D[n] [1] , D[n] [2] , D[n] [3] 으로 식을 세우는 것이다.

왜냐하면 1+1+1 처럼, 연속된 수는 못오기 때문이다.

1 앞에는 2, 3만 올 수 있다.

2 앞에는 1, 3만 올 수 있다.

3 앞에는 1, 2만 올 수 있다.

n = 6인 경우를 보자.

D[6] [1] 을 구하기 위해서는 6에서 1을 뺀 D[5] 라인을 살펴봐야 한다.

왜냐하면 1 앞에는 2와 3이 올 수 있으므로, n에서 1을 뺀 5의 경우의 수를 봐야 한다.

2가 마지막에 오는 경우의 수 D[5] [2] 와 + 3이 마지막에 오는 경우의 수 D[5] [3] 를 더하면 D[6] [1] 이 된다.

2가 마지막에 오는 경우의 표현들 D[5] [2] 뒤에 +1 을 해주면 6이 된다.

3이 마지막에 오는 경우의 표현들 D[5] [3] 뒤에 + 1 해주면 6이 된다.

마찬가지로 D[6] [2] 를 구하기 위해서는 6에서 2를 뺀 D[4] 라인을 살펴봐야 한다.

왜냐하면 2 앞에는 1과 3이 올 수 있는데, 4에서 1과 3으로 끝난 경우의 수들을 봐야 하기 때문이다.

그래서 1이 마지막에 오는 경우의 수 D[4] [1] 과 3이 마지막에 오는 경우의 수 D[4] [3] 를 더하면 D[6] [2] 이 된다.

점화식은 아래와 같다.

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

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

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

코드

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


long long D[100001][4]; 

long long sum_case(int num){

    int i = 0;

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

    return (D[num][1] + D[num][2] + D[num][3])  % MODNUM;

}

int main(void){

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

    int test_case, n = 0, num = 0;

    D[1][1] = D[2][2] = 1;

    D[3][1] = 1;
    D[3][2] = 1;
    D[3][3] = 1;

    scanf("%d", &test_case);

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

    return 0;
}

마지막으로 mod 연산 때문에 틀려서 참고한 코드가 있다.

sum_case() 의 반환값도 long long, D배열의 반환값도 long long으로 해야 맞출 수 있었다.

문제

카드구매하기2 백준 16194번

리뷰

이전에 풀었던 카드구매하기 문제와는 반대로 '최소값'을 구하는 문제다.

[P[i] 에는 카드팩의 값을 저장한다.

MinCost[i] 에는 i장을 샀을 때의 최소값을 저장하는데, 처음에는 P[i] 값을 저장하고 시작한다.

4장을 산다면,

MinCost[1] + P[3] 와 MinCost[4] 를 비교한다.

MinCost[2] + P[2] 와 MinCost[4] 를 비교한다.

MinCost[3] + P[1] 와 MinCost[4] 를 비교한다.

코드

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

int P[10001];
int MinCost[1001];

int main(void){

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

    int n = 0, input = 0;

    scanf("%d", &n);

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

    MinCost[1] = P[1];    

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

        MinCost[i] = P[i];

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

            int temp = min(MinCost[i], MinCost[i-j] + P[j]);

            if(temp < MinCost[i]){
                MinCost[i] = temp;
            }
        }
    }

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

    return 0;
}

문제

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

리뷰

정수 1 부터 "1, 2, 3 의 합으로 나타내는 방법의 수" 를 전부 적어봤다.

정수 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>
using namespace std;

int arr[12];

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];
    }

    return arr[num];
}

int main(void){

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

    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;
}

문제

이친수 백준 2193번

리뷰

0 뒤에는 0, 1 둘 다 올 수 있고, 1 뒤에는 반드시 0이 와야한다. (1이 연속되면 안되는 규칙 때문)

앞서 풀었던 쉬운계단수문제 와 비슷한 아이디어로 풀었다.

N자리 수의 마지막 자리 숫자가 0인 경우, N자리 수의 마지막 자리 숫자가 1인 경우의 규칙을 찾는 것이다.

1자리, 2자리 , ... 7자리 까지 이친수 경우를 써보면 발견할 수 있었다.

1자리 -> 1 arr[1] [1] = 1

2자리 -> 10 arr[2] [0] = 1

3자리 -> arr[3] [0] = 1 , arr[3] [1] = 1 100, 101

4자리 -> arr[4] [0] = 2, arr[4] [1] = 1 1000, 1001, 1010

5 자리 -> arr[5] [0] = 3, arr[5] [1] = 2 10010, 10001, 10000, 10101, 10100

6자리 -> arr[6] [0] = 5, arr[6] [1] =3

아래와 같은 점화식을 만들 수 있다.

    arr[i][0] = arr[i-1][0] + arr[i-2][0];
    arr[i][1] = arr[i-1][0];

코드

#include <stdio.h>
using namespace std;

 // 이친수 (2193)

long long arr[91][2];

int main(void){

    int n = 0;
    int i = 0;

    scanf("%d", &n);

    arr[1][1] = 1;

    arr[2][0] = 1;

    arr[3][0] = 1;
    arr[3][1] = 1;

    for(i = 4; i <= n; i++){
        arr[i][0] = arr[i-1][0] + arr[i-2][0];
        arr[i][1] = arr[i-1][0];
    }

    printf("%lld", arr[n][0] + arr[n][1]); // 답 출력할 때 long long 자료형 

    return 0;
}

문제

오르막 수 백준 11057번

리뷰

'쉬운 계단 수' 문제 보다 고려할 것이 적었다.

숫자가 반드시 1씩 연속되어야 하는것도 아니고, 인접한 수가 같아도 오름차순으로 친다.

ex) 2234, 3678, 11119

[ 점화식 ]

자리수 N의 숫자들의 마지막 자리 숫자가 L이라고 한다.

**arr [2] [3] 은 2자리 숫자 중에 마지막 자리 숫자가 3인 계단 수의 개수다. ex) 13, 23, 33

arr [N] [L] 을 구할 때, arr[N-1] [k]의 개수를 누적하는데, 이 때 k는 0부터 j이다.

2자리 숫자들 중에 마지막 자리 숫자가 '7' 이라면, k는 0부터 7까지다.

arr [N] [L] = arr [N-1] [0] + arr [N-1] [1] + arr [N-1] [2] + ... + arr [N-1] [6] + arr [N-1] [k]

오르막 수는 0부터 시작 가능하다.

코드

#include <stdio.h>
using namespace std;

// 오르막 수  (BOJ 11057) 

int arr[1001][10];

int main(void){

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

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

    scanf("%d", &n);

    for(i = 0; i <= 9; i++){ // 1자리 수는 전부 1개  
        arr[1][i] = 1;
    }

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

        for(j = 0; j <= 9; j++){ // 0 부터 시작 가능 

            for(int k = 0; k <= j; k++){ 
                // j=3 이라면, 마지막 수k로 0, 1, 2, 3 올 수 있다.  
                arr[i][j] += arr[i-1][k];
            }    

            arr[i][j] %= 10007;
        }    
    }

    for(i = 0; i <= 9; i++){
        sum += arr[n][i];
    }    

    printf("%d", sum % 10007);

    return 0;
}

문제

쉬운 계단 수 백준 10844번

리뷰

자리수 N이 1일 때, 2일 때의 계단 수들을 써봤다.

자리수 마다의 계단 수 합계에 규칙성이 있을 것 같았는데, 그렇지 않았다.

'0'은 반드시 앞에 1이 와야 하는 제한이 있고, ex) 10, 210

'9'는 반드시 앞에 8이 와야 하는 제한이 있었다. ex) 89, 789

0, 9와는 달리, '1'은 앞에 2가 와도 되고 0이 와도 된다. (이렇게 1부터 8까지는 제한이 없다.)

마지막 자리 숫자가 L인 계단수가 몇개인지를 기준으로 점화식이 필요하다.

[ 점화식 ]

자리수 N의 숫자들의 마지막 자리 숫자가 L이라고 한다.

arr [2] [3] 은 2자리 숫자 중에 마지막 자리 숫자가 3인 계단 수의 개수다. ex) 23, 43 이 된다.

arr [N] [L] = arr [N-1] [L-1] + arr [N-1] [L+1]

이 때, L의 범위는 1 <= L <= 8 이다.

왜냐하면 '0'은 앞에 1이 와야만 하고, '9'는 앞에 8이 와야만 하니까 따로 관리한다.

(계단 수는 0으로 시작하지 않음)

1자리 수과 2자리 수의 계단 수 개수

2자리 수 중에서(N = 2) , 마지막 자리 숫자가 2인 경우(L = 2)를 보면, 12와 32가 있다.

2 앞에는 1과 3이 올 수 있다.

즉, 1자리 숫자에서 마지막 자리 숫자가 1인 계단수의 개수, 마지막 자리 숫자가 3인 계단수의 개수 가 몇 개냐에 따라 결정된다.

식으로 정리하면 , arr [2] [2] = arr [1] [1] + arr [1] [3]

arr [N] [L] = arr [N-1] [L-1] + arr [N-1] [L+1]

그리고 유의할 점.

1000000000 으로 나눈 값을 출력해야 하니까, 배열에 저장할 때 부터 mod 연산을 해야 한다.

처음에는 sum을 int로 선언했었는데, 1000000000 때문에 long long을 바꾸니까 맞았다.

코드

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

int arr[101][11];

int main(void){

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

    scanf("%d", &n);

    for(i=1; i<=9; i++){  // 0을 제외한 1자리 수들은 모두 계단 수가 1개.
        arr[1][i] = 1;
    }

    for(i = 2; i <= n; i++){ //  n : 몇 자리 수 인지  

        for(j=0; j <= 9; j++){ //  숫자의 마지막 자리 수  

            if(j == 0) 
                arr[i][0] = arr[i-1][1] % MODNUM;
            else if(j == 9) 
                arr[i][9] = arr[i-1][8] % MODNUM;
            else 
                arr[i][j] = ( arr[i-1][j-1] + arr[i-1][j+1] ) % MODNUM;
        }
    }

    for(i = 0; i <= 9; i++){  
        sum += arr[n][i];
    }

    printf("%lld", sum % MODNUM); // 마지막에 mod 연산 

    return 0;
}