9095 1,2,3 더하기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

1, 2, 3 더하기성공

한국어   

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

128 MB

38192

24218

16241

61.640%

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1 복사

3 4 7 10

예제 출력 1 복사

7 44 274

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 PC번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: standardraccoon wjrqur1200

 

<개인풀이>

각

1 1

2 (1+1), 2

3 (1+1+1), (2+1), (1+2), 3

4 (1+1+1+1), (2+1+1),(1+2+1),(1+1+2), (2+2), (3+1) ,(1+3) 

 

1의 1로 2의 1+ x 의 수를 만들 수 있고, 3의 1+ x들을 만들 수 있다.

 

좀더 자세히 예를들면

3의 예)

  1+1+1은 2의 (1+1)에 파생된 수 1번,

  (2+1)은 2를 만들때 필요한 2를 사용한 수 1번,

  (1+2)는 1의 1에 2를 더한 수 1번, 

  새로운 3 수 1번, 

  sum = 4번

 

4의 예

 3의(1+1+1)에 +1하는 1번,

 3의(2+1)에 +1하는 1번,

 3의 (1+2)에 +1 하는 1번,

 3의 3에 +1 하는 1번,

 

 2의 (1+1)에 +2 하는 1번,

 2의 2에 +2 하는 1번,

 

 1의 1에 +3 하는 1번

 

 sum = 7번 으로 점화식은 피보나치와 유사하게 이이이전, 이이전, 이전 횟수를 더하는 경우의 수와 같은

 d[n] = d[n-3] +d[n-2]+d[n-1] 식을 지님.

 

#include<stdio.h>
 
static unsigned int d[11] = { 0, };
 
 
 
int main(void)
{
    int get_line = 0, get_num = 0;
    d[0] = 1;
    d[1] = 1;
    d[2] = 2;
    
 
    //d[n] = d[n-3]+d[n-2]+d[n-1];
    for (int i = 3; i < 11; ++i)
    {
        d[i] = d[i - 1] + d[i - 2] + d[i - 3];
    }
    
    scanf("%d", &get_line);
 
    for (unsigned short i = 0; i < get_line; ++i)
    {
        scanf("%d", &get_num);
        printf("%d\n", d[get_num]);
    }
    return 0;
}