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]