15989 : 1, 2, 3 더하기 4

풀이

계단오르기 문제랑 비슷하게 풀면 된다

중복되는 경우를 배제해야 하므로

2칸 오르는 경우의 수와 3칸 오르는 경우의 수를 따로 구해주자

답은 두 값을 합친 거에 1로만 채우는 경우의 수 1을 더해주면 된다.

코드

#include <cstdio>
int n, t, d[2][10001];
int main() {
    d[0][2] = 1;
    for (int i = 3; i <= 10000; i++) {
        d[0][i] = d[0][i-2]+1;
        d[1][i] = d[0][i-3]+d[1][i-3]+1;
    }
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        printf("%d\n", 1+d[0][n]+d[1][n]);
    }
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-07 16:22

Read more posts by this author