[BOJ알고리즘, C++]#9095_1, 2, 3 더하기, DP

2024. 3. 3. 08:21· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. DP, 동적 계획법
  4. 2. 현재 숫자의 -1, -2, -3 숫자의 결과 값을 모두 더하자!
  5. #3. 코드

 

#1. 문제

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

 

9095번: 1, 2, 3 더하기

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

www.acmicpc.net

 


 

#2. 풀이

 

1. DP, 동적 계획법

https://webddevys.tistory.com/311

 

[알고리즘]#5_동적 계획법

[알고리즘]#5_동적 계획법 동적 계획 알고리즘에 대해 알아보겠습니다. Overview 개념 예제 #0. 개념 1. 동적 계획법(Dynamic Programming) 동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디

webddevys.tistory.com

 

2. 현재 숫자의 -1, -2, -3 숫자의 결과 값을 모두 더하자!

 

  1. 총 세 가지 숫자를 통해 현재 숫자를 만들려면, 현재 숫자 - 1, 현재 숫자 -2, 그리고 현재 숫자 - 3 값의 경우의 수를 모두 더해줍니다.
  2. 0 ~ 3 까지의 결과 값을 미리 DP 배열에 삽입해 주고, 4부터 주어진 n 값까지 DP를 수행해 주어, 최종적으로 숫자 n에 대한 모든 경우의 수를 출력해 줍니다.

 


 

#3. 코드

 

/*
    @문제 : 1, 2, 3의 합으로 숫자 n을 구할 수 있는 경우의 수
    @설명
            1. n에 대한 경우의 수는 dp[n-1] + dp[n-2] + dp[n-3] 과 같다
            2. 점화식, dp[n] = dp[n-1] + dp[n-2] + dp[n-2], when n > 3
*/

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int T, n;
int dp[11] = {
    0,
    1,
    2,
    4,
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    while (T--)
    {
        cin >> n;

        if (n < 4)
        {
            cout << dp[n] << '\n';
            continue;
        }

        for (int i = 4; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        cout << dp[n] << '\n';
    }

    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#15681_트리와 쿼리, 트리, DFS, DP  (0) 2024.03.03
[BOJ알고리즘, C++]#2533_사회망 서비스, 트리, DP  (1) 2024.03.03
[BOJ알고리즘, C++]#1463_1로 만들기, DP, 동적 계획법  (0) 2024.02.26
[BOJ알고리즘, C++]#10026_적록색약, 그래프 탐색, DFS, 재귀 호출, 영역 찾기  (1) 2024.02.26
[BOJ알고리즘, C++]#1012_유기농 배추, 그래프 탐색, BFS, 영역 찾기  (0) 2024.02.26
  1. #1. 문제
  2. #2. 풀이
  3. 1. DP, 동적 계획법
  4. 2. 현재 숫자의 -1, -2, -3 숫자의 결과 값을 모두 더하자!
  5. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#15681_트리와 쿼리, 트리, DFS, DP
  • [BOJ알고리즘, C++]#2533_사회망 서비스, 트리, DP
  • [BOJ알고리즘, C++]#1463_1로 만들기, DP, 동적 계획법
  • [BOJ알고리즘, C++]#10026_적록색약, 그래프 탐색, DFS, 재귀 호출, 영역 찾기
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 최단 경로
  • C++
  • 개발
  • set
  • 디자인 패턴
  • 알고리즘
  • 우선순위 큐
  • stl
  • dfs
  • 정렬
  • BFS
  • Effective C++
  • DP
  • Unreal Blueprint
  • 트리
  • 기술 질문
  • 그래프
  • unreal
  • BOJ
  • programmers

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#9095_1, 2, 3 더하기, DP
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.