본문 바로가기
PS(Problem Solving)/백준_BOJ

[백준] 2579번 - 계단 오르기(C++/파이썬) 문제 및 풀이

by 초코칩프라푸치노 2021. 4. 9.

문제) 백준 - 동적 계획법 (Dynamic Programming) - 계단 오르기

-> www.acmicpc.net/problem/2579

 

2579번: 계단 오르기

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

www.acmicpc.net

 

Python 코드는 바텀업(Bottom-Up), C++코드는 탑다운(Top-Down)으로 구현했다.

 

 

 

C++ 소스 코드)

 

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
int n;
int cache[301];
int stairs[301];
int stair(int i) {
//기저 사례
if (i < 0) return 0;
//Memoization
int& ret = cache[i];
if (ret != -1) return ret;
//Ans
ret = max(ret, stair(i - 2) + stairs[i]);
ret = max(ret, stair(i - 3) + stairs[i - 1] + stairs[i]);
return ret;
}
int main() {
ios::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)cin >> stairs[i];
memset(cache, -1, sizeof(cache));
cout << stair(n - 1);
return 0;
}
view raw 2579.cpp hosted with ❤ by GitHub

 

 

Python 소스 코드)

 

n = int(input())
score = [0] * 301
dp = [0] * 301
for i in range(n):
score[i] = int(input())
dp[0] = score[0]
dp[1] = score[0] + score[1]
dp[2] = max(score[0] + score[2], score[1] + score[2])
for i in range(3, n):
dp[i] = max(dp[i-3] + score[i-1] + score[i], dp[i-2] + score[i])
print(dp[n-1])
view raw 2579.py hosted with ❤ by GitHub

 

반응형

댓글