문제) 백준 - 동적 계획법 (Dynamic Programming) - 계단 오르기
-> www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
Python 코드는 바텀업(Bottom-Up), C++코드는 탑다운(Top-Down)으로 구현했다.
C++ 소스 코드)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Python 소스 코드)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]) |
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
[백준] 2437번 - 저울 (C++/파이썬) (0) | 2021.04.13 |
---|---|
[백준] 2503번 - 숫자야구 (C++) 문제 및 풀이 (0) | 2021.04.13 |
[백준] 1629번 - 곱셈 (C++) 문제 및 풀이 (0) | 2021.04.09 |
[백준] 2217번 - 로프 (파이썬/C++) 문제 및 풀이 (0) | 2021.04.05 |
[백준] 11726번 - 2xn 타일링 (파이썬/C++) 문제 및 풀이 (0) | 2021.03.30 |
댓글