풀이
계단오르기 문제랑 비슷하게 풀면 된다
중복되는 경우를 배제해야 하므로
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이