📖 백준 2096번 : https://www.acmicpc.net/problem/2096
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 4 MB |
문제
N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다.
숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.
풀이
모든 경로를 계산하는 것은 기하급수적으로 커지는 경우의 수 때문에 시간 제한을 맞출 수 없다. 주어진 입력 N이 100,000인 것을 보고 최소한 O(NlogN)의 복잡도를 가지는 코드를 구현해야 한다는 생각이 들었다. 따라서 bfs, 백트래킹 등 모든 경우의 수를 탐색하고 최소, 최댓값을 구분하는 것은 제외했다.
모든 경로를 계산할 수 없기 때문에, 문제에서 최소와 최댓값만을 요구한다는 점에 집중했다. 모든 경로의 값을 계산하지 말고 각 위치까지의 최소, 최댓값을 계산하면 O(N)의 복잡도로 계산이 가능할거란 생각이 들었다. 따라서 나는 각 위치의 구간합을 계산해서 최소, 최댓값을 dp로 갱신하는 방식을 생각했다. 문제의 조건에서 메모리 제한이 4mb이므로 주어진 모든 정보를 저장하는 배열을 사용할 수 없다는 점을 주의해야한다.
각각의 깊이에서 주어지는 3개의 숫자에 대한 최소, 최댓값의 구간합을 dpMinA, dpMinB, dpMinC, dpMaxA, dpMaxB, dpMaxC변수가 저장한다. 예를 들자면 dpMinA는 현재 깊이의 첫번째 숫자에서 가질 수 있는 구간합의 최솟값을 의미한다. 값이 입력될 때마다 구간합을 갱신하면서 최소, 최댓값을 유지한다. 마지막으로 가장 큰 값과 작은 값을 골라 출력하면 끝이다.
좀 더 자세히 설명하자면, 각 깊이의 3개의 위치에서 가질 수 있는 구간합들의 최소 최대에만 집중하는 것이다. k번째 위치에서 무수히 많은 경로의 구간합이 존재하지만 최소, 최대 구간합은 각각 하나만 존재한다. k번째 위치의 처음 숫자에서 가질 수 있는 구간합의 최소는 다음과 같은 식으로 표현 가능하다.
EX) dp[k][0] = min(dp[k-1][0], dp[k-1][1]) + a; 각 dp는 최소 구간합을 저장한다. k번재 깊이의 첫번째 숫자에서는 k-1번째 깊이의 첫번째 숫자의 최소 구간합, 두번째 숫자의 최소 구간합 중 더 작은 값 + 현재값으로 정의할 수 있다.
이러한 점화식을 각각의 경우에 알맞게 6가지 식을 작성하면 답을 구해낼 수 있다.
각각의 계산에서 바로 구간합을 갱신하면 다른 구간합을 계산할 때 값이 변형된다. 따라서 구간합들을 계산할 때 minTempA등과 같은 임시변수를 활용해 바로 값을 변경하지말고 저장해뒀다가 한번에 반영하는 형태로 구현했다.
코드
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
int a,b,c;
int maxTempA, maxTempB, maxTempC, minTempA, minTempB, minTempC;
cin >> n;
cin >> a >> b >> c;
//각 위치에서의 구간합의 최대
int dpMaxA = a;
int dpMaxB = b;
int dpMaxC = c;
//각 위치에서의 구간합의 최소
int dpMinA = a;
int dpMinB = b;
int dpMinC = c;
for (int i = 1; i < n; i++) {
cin >> a >> b >> c;
//최대 구간합 계산
maxTempA = a + max(dpMaxA, dpMaxB);
maxTempB = b + max(max(dpMaxA, dpMaxB), dpMaxC);
maxTempC = c + max(dpMaxB, dpMaxC);
//최대 구간합 갱신
dpMaxA = maxTempA;
dpMaxB = maxTempB;
dpMaxC = maxTempC;
//최소 구간합 계산
minTempA = a + min(dpMinA, dpMinB);
minTempB = b + min(min(dpMinA, dpMinB), dpMinC);
minTempC = c + min(dpMinB, dpMinC);
//최소 구간합 갱신
dpMinA = minTempA;
dpMinB = minTempB;
dpMinC = minTempC;
}
int maxAns = max(max(dpMaxA, dpMaxB), dpMaxC);
int minAns = min(min(dpMinA, dpMinB), dpMinC);
cout << maxAns << ' ' << minAns;
return 0;
}