본문으로 바로가기

임의의 수를 1, 2, 3의 덧셈으로 조합할 경우 제일 첫 번째로 오는 수가 1인 경우, 2인 경우, 3인 경우로 생각해볼 수 있다. 다이나믹 프로그래밍을 사용하여 중복 계산을 피하고 한 번 구한 값은 배열에 저장한다.

#include <cstdio>

int dp[11];
int f(int);

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    printf("%d\n", f(n));
  }
  return 0;
}

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  if (n == 3) return 4;
  if (dp[n]) return dp[n];

  // 1로 시작하는 경우 f(n-1) +
  // 2로 시작하는 경우 f(n-2) +
  // 3으로 시작하는 경우 f(n-3)
  return dp[n] = f(n-1) + f(n-2) + f(n-3);
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 10844: 쉬운 계단 수  (0) 2018.05.15
[BOJ] 11052: 붕어빵 판매하기  (0) 2018.05.15
[BOJ] 9095: 1, 2, 3 더하기  (0) 2018.05.15
[BOJ] 11727: 2xn 타일링 2  (0) 2018.05.15
[BOJ] 11726: 2xn 타일링  (0) 2018.05.15
[BOJ] 1463: 1로 만들기  (0) 2018.05.15

댓글을 달아 주세요