Difference between r1.2 and the current
@@ -86,8 +86,10 @@
== 박인서 ==
* Dynamic Programming
* dp[j][i] - i번째 계단까지 오르는데 그 직전에 밑계단에서 올라왔다면 j=1, 아니면 j=0이다.
* dp[0][i]=max(dp[0][i-2],dp[1][i-2])+st[i]
* dp[1][i]=dp[1][i-1]+st[i]
{{{
* dp[k][i] - i번째 계단까지 오르는데 그 직전에 밑계단에서 올라왔다면 k=1, 아니면 k=0이다.
* dp[0][i] = max(dp[0][i-2],dp[1][i-2])+st[i]
* dp[1][i] = dp[1][i-1]+st[i]
}}}
== 곽정흠 ==
3.1. 15이원준 ¶
#include<iostream>
#include<algorithm>
using namespace std;
int N;
int arr[301] = { 0, };
int dp[301][3] = { 0, };
int main(){
cin>> N;
for(int i = 1; i<=N; i++){
scanf("%d", &arr[i]);
}
if(N < 3){
int ans = 0;
for(int i = 1; i<=N; i++){
ans += arr[i];
}
cout<< ans << endl;
return 0;
}
dp[1][1] = arr[1];
dp[2][1] = arr[2];
dp[2][2] = dp[1][1] + arr[2];
for(int i = 3; i<=N; i++){
dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + arr[i];
dp[i][2] = dp[i-1][1] + arr[i];
}
int ans = 0;
ans = max(dp[N][2] , dp[N][1]);
cout<< ans <<endl;
}
3.2. 박인서 ¶
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> dp[2], st;
int main() {
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
int t;
std::cin >> t;
st.push_back(t);
}
dp[0].push_back(0);
dp[0].push_back(st[1]);
dp[1].push_back(st[0]);
dp[1].push_back(st[0] + st[1]);
for (int i = 2; i < n; i++) {
dp[0].push_back(std::max(dp[0][i - 2], dp[1][i - 2]) + st[i]);
dp[1].push_back(dp[0][i - 1] + st[i]);
}
std::cout << std::max(dp[0][n - 1], dp[1][n - 1]);
return 0;
}
4.1. 15이원준 ¶
- dp를 이용하여 풀었습니다.
- 각 계단의 상태는 연속해서 1번 밟은 상태이거나 2번 밟은 상태일 수있습니다.
- 1번 밟은 상태는 밑밑 계단에서 2계단 오른 것입니다. 이는 3번연속 밟는 것과 상관이 없으므로 밑밑 계단에서 두 상태 중 더 큰 값을 갖는 것을 가져와 현 계단의 값을 더여 1번 밟은 상태에 저장합니다.
- 2번 밟은 상태는 밑 계단에서 1계단 오른 것입니다. 이는 3번 연속 밟는 것과 상관이 있으므로 밑 계단에서 1번 밟은 상태의 값에 현 계단의 값을 더하여 2번 밟은 상태에 저장합니다.
- 이를 반복하여 끝 계단의 1번 밟은 상태와 2번 밟은 상태의 값 중 큰 값을 출력합니다.
