«   2022/10   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
Archives
Today
0
Total
96,326
관리 메뉴

차근차근

[백준 9461] 파도반 수열 본문

대학교/Algorithm

[백준 9461] 파도반 수열

SWKo 2020. 3. 13. 02:27

0. 제목

  • 백준 9461 파도반 수열
  • BOJ 9461 파도반 수열
  • C++ 9461 파도반 수열

1. 문제

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


2. 풀이

  • 점화식을 찾으면 쉽게 풀리는 문제이다.
  • 두가지 점화식으로 풀리는데 다음과 같다.
  • dp[i] = dp[i-2] + dp[i-3]
  • dp[i] = dp[i-1] + dp[i-5]
  • 두가지 중 하나로 코드를 짜면 정답이다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int T, N;
    long int dp[101= {0};
    cin >> T;
    
    dp[1= 1;
    dp[2= 1;
    dp[3= 1;
    for(int j = 4; j <= 100; j++)
        dp[j] = dp[j-2+ dp[j-3];
    
    for(int i = 0; i < T; i++){
        cin >> N;
        cout << dp[N] << '\n';
    }
    
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 6378] 디지털 루트  (0) 2020.03.15
[백준 2225] 합분해  (0) 2020.03.14
[백준 1167] 트리의 지름  (0) 2020.03.11
[백준 11725] 트리의 부모 찾기  (0) 2020.03.11
[백준 2869] 달팽이는 올라가고 싶다  (0) 2020.03.09
0 Comments
댓글쓰기 폼