https://www.acmicpc.net/problem/2096
2096번: 내려가기
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
www.acmicpc.net
문제 특성상 메모리가 아주 제한되어있다.
dp값을 2차원 배열에 모두 저장하기에는 제한 조건을 초과하므로,
dp값을 계산하는 1차원 배열(dp_min, dp_max)과
dp값을 잠시 저장하는 1차원 배열(tmp)을
사용하여 재활용해가며 값을 구하자.
맞왜틀 당해서 지우고 다시 코드짜보니 ac받을 수 있었다.
#include<bits/stdc++.h>
using namespace std;
int arr[100100][3];
int tmp[3], dp_max[3], dp_min[3];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
//입력
for(int i=0; i<n; i++)
cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
//배열 초기값 설정
tmp[0] = dp_max[0] = arr[0][0];
tmp[1] = dp_max[1] = arr[0][1];
tmp[2] = dp_max[2] = arr[0][2];
/*
점화식 돌리기
1. [i][0]는 [i-1][0], [i-1][1]로부터 올 수 있다.
2. [i][1]는 [i-1][0], [i-1][1], [i-1][2]로부터 올 수 있다.
3. [i][2]는 [i-1][1], [i-1][2]로부터 올 수 있다.
*/
//최댓값 구하기
for(int i=1; i<n; i++){
dp_max[0] = max(tmp[0], tmp[1]) + arr[i][0];
dp_max[1] = max(tmp[0], max(tmp[1],tmp[2])) + arr[i][1];
dp_max[2] = max(tmp[1], tmp[2]) + arr[i][2];
tmp[0] = dp_max[0];
tmp[1] = dp_max[1];
tmp[2] = dp_max[2];
}
//최대값 출력
cout << max(dp_max[0],max(dp_max[1],dp_max[2])) << ' ';
//배열 초기값 설정
tmp[0] = dp_min[0] = arr[0][0];
tmp[1] = dp_min[1] = arr[0][1];
tmp[2] = dp_min[2] = arr[0][2];
//최솟값 구하기
for(int i=1; i<n; i++){
dp_min[0] = min(tmp[0], tmp[1]) + arr[i][0];
dp_min[1] = min(tmp[0], min(tmp[1],tmp[2])) + arr[i][1];
dp_min[2] = min(tmp[1], tmp[2]) + arr[i][2];
tmp[0] = dp_min[0];
tmp[1] = dp_min[1];
tmp[2] = dp_min[2];
}
//최솟값 출력
cout << min(dp_min[0],min(dp_min[1],dp_min[2]));
return 0;
}
'문제 풀이' 카테고리의 다른 글
[c++] 백준 2138 전구와 스위치 (0) | 2023.03.13 |
---|---|
[c++] 백준 9251 LCS (0) | 2023.03.08 |
[c++] 백준 2294 동전 2 (0) | 2023.03.07 |
[c++] 백준 13164 행복 유치원 (0) | 2023.03.07 |
[c++] 백준 1041 주사위 (0) | 2023.03.06 |