고도고도
초록 로봇 🤖
고도고도
전체 방문자
6,070
오늘
0
어제
7
  • 분류 전체보기 (137)
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (33)
      • TIL (13)
      • Android (4)
      • Kotlin (4)
      • Flutter (5)
      • Node.js (5)
      • Error (2)
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (42)
      • Math (1)
      • Implementation (2)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (0)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (50)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (7)

블로그 메뉴

  • 홈
  • 깃허브

인기 글

  • 5. SingleChildScrollView, Lis⋯
    2021.08.18
  • [TIL] 22.03.13
    2022.03.13
    [TIL] 22.03.13
  • [문자열 / Kotlin] 2020 KAKAO⋯
    2022.03.11
    [문자열 / Kotlin] 2020 KAKAO⋯
  • [TIL] 22.03.20
    2022.03.20
    [TIL] 22.03.20
  • [투포인터 / Kotlin] BOJ 3273⋯
    2021.12.25
    [투포인터 / Kotlin] BOJ 3273⋯

최근 글

  • [Android] MVVM 패턴 적용기 - 2
    2022.05.14
    [Android] MVVM 패턴 적용기 - 2
  • [코틀린 완전정복] 공변성, 반⋯
    2022.05.02
    [코틀린 완전정복] 공변성, 반⋯
  • [코틀린 완전정복] 제네릭
    2022.04.25
    [코틀린 완전정복] 제네릭
  • [코틀린 완전정복] 여러 종류의⋯
    2022.04.23
    [코틀린 완전정복] 여러 종류의⋯
  • [코틀린 완전정복] 추상 클래스⋯
    2022.04.22
    [코틀린 완전정복] 추상 클래스⋯

최근 댓글

  • 잘보고 갑니다~
    개갓세
  • 좋은 글이네요
    날인로세
  • 잘 보고 갑니다^^
    프로퍼티
hELLO · Designed By 정상우.
고도고도

초록 로봇 🤖

[동적 계획법 1] [C++] 2579번. 계단 오르기
✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 2579번. 계단 오르기

2021. 1. 14. 10:28

www.acmicpc.net/problem/2579

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

 

 

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.


해결 방법

dp 문제이므로 점화식을 찾아야한다.

도착지점에 갈 수 있는 방법은 어떻게 될까? 두 가지로 나눌 수 있다.

 

i) 전 계단을 밟고 도착 지점을 밟는 경우

ii) 전전 계단을 밟고 도착 지점을 밟는 경우

 

이렇게 두 가지로 나눌 수 있는데 주의할 점은 연속된 3개의 계단은 밟을 수 없다는 것이다.

 

즉, i) 에서 전 계단을 밟기 이전에 전전 계단을 밟을 수 없고, 무조건 전전전 계단을 밟아야한다는 것이다.

 

따라서 이 조건을 점화식으로 나타내면

i) 전전전 계단의 최대값 + 전 계단 + 도착 계단 = dp[i-3] + stair[i-1] + stair[i]

ii) 전전 계단의 최대값 + 도착 계단 = dp[i-2] + stair[i]

위와 같이 나타낼 수 있다.

 

 

해결 과정

위의 점화식을 반복문을 통해 탐색하면 된다. 여기서 한 가지 더 주의할 점이 있다.

점화식을 살펴보면 dp[i-3], dp[i-2] 이므로 반복문의 시작 index 값을 i≥3 으로 잡아줘야 한다는 것이다.

따라서 dp[0], dp[1], dp[2]를 미리 선언해놓을 필요가 있다.

 

해당 계단까지의 최대 값을 저장해놓은 배열이 dp라고 할 때 아래와 같이 나타낼 수 있다.

dp[0] = stair[0]

dp[1] = max(stair[1], stair[0] + stair[1])

dp[2] = max(stair[0] + stair[1], stair[1] + stair[2])

여기서 max함수는 최대 값을 return하는 함수이다.

 

최종 코드는

 

#include <iostream>
using namespace std;


int max(int a, int b){
    return a > b ? a : b;
}

int main(){
    int n;
    int stair[300], dp[300];
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> stair[i];
    }
    
    dp[0] = stair[0];
    dp[1] = max(stair[1], stair[0] + stair[1]);
    dp[2] = max(stair[0] + stair[2], stair[1] + stair[2]);
    
    for(int i = 3; i < n; i++){
        dp[i] = max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]);
    }
    
    cout << dp[n-1];
    
    return 0;
}

 

 

 

저작자표시

'✍️ 코테 준비 > Dynamic Programming' 카테고리의 다른 글

[동적 계획법 1] [C++] 10844번. 쉬운 계단 수  (0) 2021.01.24
[동적 계획법 1] [C++] 1463번. 1로 만들기  (0) 2021.01.19
[동적 계획법 1] [C++] 2579번. 계단 오르기  (0) 2021.01.14
[동적 계획법 1] [C++] 1932번. 정수 삼각형  (0) 2021.01.13
[동적 계획법 1] [C++] 1149번. RGB 거리  (0) 2021.01.13
[동적 계획법 1] [C++] 9461번. 파도반 수열  (0) 2021.01.13
    '✍️ 코테 준비/Dynamic Programming' 카테고리의 다른 글
    • [동적 계획법 1] [C++] 10844번. 쉬운 계단 수
    • [동적 계획법 1] [C++] 1463번. 1로 만들기
    • [동적 계획법 1] [C++] 1932번. 정수 삼각형
    • [동적 계획법 1] [C++] 1149번. RGB 거리
    C++, 동적 계획법 1, 백준
    고도고도
    고도고도
    안드로이드 개발자가 되고 싶은 컴공생
    댓글쓰기
    다음 글
    [동적 계획법 1] [C++] 1463번. 1로 만들기
    이전 글
    [코독하구만 팀] 2020.01.13(수) - 4주차 모임 결과
    • 이전
    • 1
    • ···
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • ···
    • 137
    • 다음