JArchive 프로그래밍 일기

문제

1,2,3 더하기 9095

"맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;

int tc, n; // n은 11보다 작은 양수다.
int D[12];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> tc;
  D[1] = 1, D[2] = 2, D[3] = 4;
  for(int i = 4; i <= 11; i++){
    D[i] = D[i-1] + D[i-2] + D[i-3];
  }
  while(tc--){
    cin >> n;   cout << D[n] << '\n';
  }
  return 0;
}

리뷰

점화식 찾는것이 쉽지 않았던 문제다.
D[i] == i를 1,2,3의 합으로 나타내는 방법 개수 라고 정했다.

일단 작은 수를 써보면서 점화식을 도출해봤다.
D[1] = 1개 (1)
D[2] = 2개. (1+1, 2)
D[3] = 4개. (1+2, 2+1, 1+1+1, 3)
D[4] = 7개. (1+1+1+1, 3+1, 2+1+1, 1+2+1, 1+1+2, 1+3, 2+2)

D[3]과 D[4]만 비교해보면.
D[3] = 4개. (1+2, 2+1, 1+1+1, 3)
D[4] = 7개. (1+1+1+1, 3+1, 2+1+1, 1+2+1, 1+1+2, 1+3, 2+2)

D[3]은 3을 만드는 4개 방법이 있다.
(1+2, 2+1, 1+1+1, 3) 이 4개의 방법에 +1만 붙이면 4가 만들어진다.
(1+2 +1, 2+1 +1, 1+1+1 +1, 3 +1)

D[2]은 2을 만드는 2개 방법이 있다.
(1+1, 2) 이 2개 방법에 +2만 하면 4가 만들어진다.
(1+1 +2, 2 +2)

D[1]은 (1) 1개 방법이 있는데. 여기에 +3만하면 4가 만들어진다.

이처럼 D[1], D[2], D[3] 의 방법 개수를 더하면 D[4]가 된다.
D[i] = D[i-1] + D[i-2] + D[i-3]

문제

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