-
[백준] #2579 계단 오르기 - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 2. 15:30
문제
https://www.acmicpc.net/problem/2579
목표
가중치가 쓰인 계단이 있을때 마지막 계단까지 이동하며 얻을수 있는 최대 가중치 구하기(단, 3개연속 불가능)
풀이
점화식: dp[i] = stairs[i] + max(dp[i-2], dp[i-3] + stairs[i-1]);
즉 현재 위치한 계단에서 구해지는 최대 가중치는 현재 계단의 가중치 + max(전전 계단에서의 최대가중치, 전전전 계단에서의 최대 가중치 + 이전계단의 가중치)
=> 2칸 전에서 현재로 이동했을때의 가중치 VS 3칸전에서 현재이전계단, 현재계단을 밟을때의 가중치의 최대값이다.
코드
1. 재귀로 구현
////재귀로 구현 #include <iostream> #include <cstring> #define MAX 301 using namespace std; int N; int arr[MAX]; //dp[i]: i번째 계단에 올랐을때의 최대점수 int dp[MAX]; int func(int s) { //계단층수가 0보다 작으면 0리턴 if (s < 0) return 0; int &ref = dp[s]; if (ref != -1) return ref; //dp[i]: 전전계단에서 현재계단으로 온경우 VS 전전전계단에서 전계단으로, 현재계단으로 온경우 ref = max(ref, func(s-2) + arr[s]); ref = max(ref, func(s-3) + arr[s-1] + arr[s]); return ref; } int main() { cin >> N; for (int i=0; i<N; ++i) { cin >> arr[i]; } memset(dp, -1, sizeof(dp)); // dp[0] = arr[0]; // dp[1] = arr[0]+arr[1]; // dp[2] = arr[0]+arr[2]; cout << func(N-1); // cout << '\n' << '\n'; // for (int i=0; i<N; ++i) { // cout << dp[i] << '\n'; // } }
2. 반복으로 구현
#include <iostream> #include <vector> #define MAX 301 using namespace std; int N; int dp[MAX]; int arr[MAX]; int func() { dp[0] = arr[0]; dp[1] = arr[1] + arr[0]; dp[2] = arr[2] + max(arr[0], arr[1]); for (int i=3; i<N; ++i) { dp[i] = arr[i] + max(dp[i-2], arr[i-1] + dp[i-3]); } return dp[N-1]; } int main() { cin >> N; for (int i=0; i<N; ++i) { cin >> arr[i]; } cout << func(); }
'Algorithm > 알고리즘 백준 풀이' 카테고리의 다른 글
[백준] #9252 LCS2(Longest Common Subsequence) - (DP) (0) 2020.03.02 [백준] #11659 구간합 구하기4 - (DP) (0) 2020.03.02 [백준] #1932 정수삼각형 - (DP) (0) 2020.03.02 [백준] #1759 암호만들기 - (BF) (0) 2020.02.12 [백준] #1080 행렬 - (BF) (0) 2020.02.12