[BOJ알고리즘, C++]#2579_계단 오르기, DP

2024. 5. 21. 19:20· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. DP
  4. 2. 패턴을 파악하고, 점화식을 먼저 세우자
  5. #3. 코드

 

#1. 문제

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

 


 

#2. 풀이

 

1. DP

 

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

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

webddevys.tistory.com

DP는 입력 크기에 따라 중복되는 하위 문제들을 재귀적으로 해결하고, 결과 값을 기억함으로써 중복 계산을 방지하는 최적화 기법입니다. 대표적으로, 트리 자료구조에서 주로 활용되며 DFS 구현과 함께 활용되기도 합니다.

2. 패턴을 파악하고, 점화식을 먼저 세우자

점화식:
            dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + score[i]
            dp[i][2] = dp[i-1][1] + score[i];
  1. 먼저, 각 계단에 대하여 두 가지 경우의 결과 값을 저장해야 합니다. 하나는 해당 계단을 밟았을 경우, 다른 하나는 해당 계단을 밟지 않았을 경우입니다. 따라서, 2차원 배열 형식의 DP [MAX][MAX]가 필요합니다.

 


 

#3. 코드

/*
    @문제: 계단 오르기 게임을 통해 얻을 수 있는 최대 값
    @설명
        1. 한 칸 혹은 두 칸을 이동할 수 있다.
        2. 연속한 세 계단을 모두 밟을 수 없다.
        3. 마지막 계단은 무조건 밟아야 한다.
        4. 점화식:
            dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + score[i]
            dp[i][2] = dp[i-1][1] + score[i];
*/

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

#define MAX 301

vector<int> score;
int dp[MAX][2]; // 1: i-1번 계단을 밟지 않았을 경우, 2: i-1번 계단을 밟았을 경우
int N;

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

    cin >> N;

    score.resize(N+1);
    for(int i=1; i<=N; ++i)
    {
        cin >> score[i];
    }

    dp[1][1] = score[1];
    dp[1][2] = score[1];
    for(int i=2; i<=N; ++i)
    {
        dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + score[i];
        dp[i][2] = dp[i-1][1] + score[i];
    }

    cout << max(dp[N][1], dp[N][2]);

    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

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

[BOJ알고리즘, C++]#14502_연구소, 백트래킹, DFS, BFS  (1) 2024.06.19
[BOJ알고리즘, C++]#4256_트리, 트리의 순회, 두 가지 순회를 통해 다른 하나의 순회 찾기 유형  (0) 2024.05.21
[BOJ알고리즘, C++]#15900_나무 탈출, DFS, 깊이 우선 탐색  (0) 2024.05.21
[BOJ알고리즘, C++]#13511_트리와 쿼리2, 트리, LCA, 노드 사이 거리  (0) 2024.05.21
[BOJ알고리즘, C++]#1058_친구, 최단 경로, 길 찾기, 플로이드-워셜  (0) 2024.05.21
  1. #1. 문제
  2. #2. 풀이
  3. 1. DP
  4. 2. 패턴을 파악하고, 점화식을 먼저 세우자
  5. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#14502_연구소, 백트래킹, DFS, BFS
  • [BOJ알고리즘, C++]#4256_트리, 트리의 순회, 두 가지 순회를 통해 다른 하나의 순회 찾기 유형
  • [BOJ알고리즘, C++]#15900_나무 탈출, DFS, 깊이 우선 탐색
  • [BOJ알고리즘, C++]#13511_트리와 쿼리2, 트리, LCA, 노드 사이 거리
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

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

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#2579_계단 오르기, DP
상단으로

티스토리툴바

개인정보

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

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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