«   2022/06   »
      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    
Archives
Today
45
Total
86,235
관리 메뉴

차근차근

[백준 9095] 1,2,3 더하기 본문

대학교/Algorithm

[백준 9095] 1,2,3 더하기

SWKo 2020. 1. 20. 17:56

0. 제목

  • 백준 9095 1,2,3 더하기
  • BOJ 9095 1,2,3 더하기
  • C++ 1,2,3 더하기

1. 문제

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


2. 풀이

  • DP 방식을 이용하였다.
  • 초기값 3개(dp[1], dp[2], dp[3])를 먼저 설정하였다.
  • 1, 2, 3 을 이용하여 어떻게 기존의 값을 재사용할 수 있을까
  • dp[8]을 예로 들어보면 1을 사용했을때 dp[7], 2를 사용했을때 dp[6], 3을 사용했을때 dp[5], 이 값들을 더하면 된다.
  • dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

3. 코드

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

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

[백준 11057] 오르막 수  (0) 2020.01.22
[백준 10844] 쉬운 계단 수  (0) 2020.01.22
[백준 9095] 1,2,3 더하기  (0) 2020.01.20
[백준 11727] 2×n 타일링 2  (0) 2020.01.20
[백준 11726] 2×n 타일링  (0) 2020.01.20
[백준 1463] 1로 만들기  (0) 2020.01.20
0 Comments
댓글쓰기 폼