반응형
Notice
Recent Posts
Recent Comments
Link
뜌릅
내려가기 2096번 [백준] 본문
반응형
이번에 풀은 문제는 dp와 Sliding Window를 이용하여 풀는 문제였습니다.
문제는 1칸씩 내려가면서, bottom-top 내려오는 방식으로, 위의 dp값을 이용하여 아래의 dp값을 구하는 방식으로 풀었습니다.
메모리제한이 4메가 밖에 안되어, 입력은 반복을 할때마다 받았습니다.
#import<bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main() {
fast_io;
int n;
cin>>n;
int arr[3];
int dp_max[3];
int dp_min[3];
for(int i =0;i<3;i++){
cin>>arr[i];
dp_max[i] = dp_min[i] = arr[i];
}
int i =n-1;
while(i--){
cin>>arr[0]>>arr[1]>>arr[2];
dp_max[0] = max(dp_max[1],dp_max[0]);
dp_max[2] = max(dp_max[1],dp_max[2]);
dp_max[1] = max(dp_max[0],dp_max[2])+arr[1];
dp_max[0] += arr[0];
dp_max[2] += arr[2];
dp_min[0] = min(dp_min[1],dp_min[0]);
dp_min[2] = min(dp_min[1],dp_min[2]);
dp_min[1] = min(dp_min[0],dp_min[2])+arr[1];
dp_min[0] += arr[0];
dp_min[2] += arr[2];
}
cout<<*max_element(dp_max,dp_max+3)<<" "<<*min_element(dp_min,dp_min+3);
}
반응형
'알고리즘 > PS 문제' 카테고리의 다른 글
부분수열의 합2 1208번 [백준] (0) | 2021.11.02 |
---|---|
음악프로그램 2623번 [백준] (0) | 2021.07.01 |
트리의 순회 2263번 [백준] (2) | 2021.05.27 |
Wormhole 1865번 [백준] (0) | 2021.05.26 |
조합 2407번 [백준] (0) | 2021.05.04 |