반응형

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문제였습니다. 하지만 메모리 제한이 4MB였기 때문에 배열에 모든 값을 받고 메모제이션을 진행하게 된다면 메모리 초과가 납니다. 따라서, 수를 입력받을 때마다 값을 처리해줄 필요가 있었습니다.

 

이전에 메모제이션 한 값들과 현재 입력받은 값을 연산하고 tempMax, tempMin 에 저장해 준 후 마지막에 Max, Min에 다시 저장해주는 방법을 통해 문제를 풀었습니다.

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
 
using namespace std;
 
int N;
int Max[3];
int Min[3];
int tempMax[3];
int tempMin[3];
int dx[3] = { -1,0,1 };
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int a, b, c;
 
        scanf("%d %d %d", &a, &b, &c);
 
        tempMax[0] = max(Max[0], Max[1]) + a;
        tempMax[1] = max(Max[0], max(Max[1], Max[2])) + b;
        tempMax[2] = max(Max[1], Max[2]) + c;
        tempMin[0] = min(Min[0], Min[1]) + a;
        tempMin[1] = min(Min[0], min(Min[1], Min[2])) + b;
        tempMin[2] = min(Min[1], Min[2]) + c;
        for (int j = 0; j < 3; j++) {
            Max[j] = tempMax[j];
            Min[j] = tempMin[j];
        }
    }
 
    cout << max(Max[0], max(Max[1], Max[2])) << " " << min(Min[0], min(Min[1], Min[2]));
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3015번 - 오아시스 재결합 (C++)  (0) 2022.07.10
[ 백준 ] 11505번 - 구간 곱 구하기 (C++)  (0) 2022.07.09
[ 백준 ] 5639번 - 이진 검색 트리 (C++)  (0) 2022.07.07
[ 백준 ] 14502번 - 연구소 (C++)  (0) 2022.07.06
[ 백준 ] 2357번 - 최솟값과 최댓값 (C++)  (0) 2022.07.05

+ Recent posts

티스토리툴바