문제 이해 단계
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
N x 3 짜리 맵이 존재한다.
각 칸에는 0 ~ 9 숫자가 적혀있다.
가장 윗 칸에서 한 칸씩 내려오는데,
내려올 수 있는 방향은 바로 아래 또는 대각 방향밖에 없다.
가장 위에서 아래로 이동할 때,
얻을 수 있는 최대 점수와 최수를 구하는 문제
문제 접근 단계
예제 입력을 통해 한번 유형을 찾아보려고 해 보자.
만약 내가 마지막 층(N)행의 2번째 칸인 9를 선택했다고 해보자.
이 입력에서 해당 칸을 포함하여 나올 수 있는 최댓값을 어떻게 알 수 있을까?
9로 갈 수 있는 경우의 수는 이렇게 3가지가 나올 것이다.
여기서부터 경우의 수가 3가지로 갈라졌다. 4+9/ 5+9 / 6+9로 말이다.
여기서도 또 똑같이 고민해봐야 한다.
위에서 나온 4는 어디서 올 수 있는가?
5는 어디서 올 수 있는가?
6은 어디서 올 수 있는가?
여기서 우리는 당연히 알 수 있는 최댓값을 9 + 6 + 3 = 18이란 것을 알고 있다.
그렇다면 우리는 N번째 칸의 점수합을 알기 위해서 N번 올라가야 하는가? 그렇지 않다.
N-1번째에 값을 기억시켜 두면 된다.
이게 무슨 말이냐면 이런 식으로 하는 것이다.
2행을 각 행, 각 칸에서 나올 수 있는 최댓값으로 바꿔둔 것이다.
이런 식으로 바꿔 둔 뒤 3행으로 가보자.
위에서처럼 N-1행, N-2행..
이런 식으로 찾을 필요 없이 N-1번 행에 나올 수 있는 최댓값이 이미 합해져 있으므로,
갈 수 있는 곳 중에 제일 높은 수를 채택하면 되는 것이다.
이를 점화식으로 나타낼 수 있다.
DP [a][b] = c : a행 b칸에서 나올 수 있는 최댓값이 c
라고 한다면
DP [a][b]
= MAX(DP [a-1][b-1], DP [a-1][b], DP [a-1][b+1])이다.
이를 구현하면 되는데, 사실 여기 함정이 한 가지 더 있다.
바로 메모리 제한이 4MB이다.
여기서 N이 최대 100,000이기 때문에 arr [100000][3]이 나올 텐데,
이는 메모리 제한을 넘어간다.
DP배열을 저장하는 범위를 줄여서 저장해야 한다.
여기서 슬라이딩 윈도가 사용된다.
아래와 같이 처리할 것이다.
위치에 따라 값을 입력받고, 움직일 수 있는 값을 합쳐 가장 큰 값을 tmp에 기록해 둔다.
그리고 3번째 값까지 모두 계산되면 tmp를 dp로 덮어씌운다.
N번째까지 가면, 18이 최댓값이 되는 것을 확인할 수 있다.
이제 이를 문제 구현 단계에서 코드로 구현해 보겠다.
문제 구현 단계
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int big[3]; // 최대값을 담을 DP
int small[3]; // 최소값을 담을 DP
int N;
cin >> N;
for(int i = 1; i <= N; i++){
int btmp[3]; // 최대값 임시 배열
int stmp[3]; // 최소값 임시 배열
for(int j = 0; j < 3; j++){
int v;
cin >> v;
// 첫번째 행일 경우, 비교할 값이 없기 때문에 그대로 넣음
if(i == 1){
btmp[j] = v;
stmp[j] = v;
}
else{
// 바로 위에 있는 값을 tmp에 담음
int tmp1 = big[j] + v;
int tmp2 = small[j] + v;
// 1번 칸이 아닐 경우
if(j-1 >= 0){
tmp1 = max(tmp1,big[j-1]+v);
tmp2 = min(tmp2,small[j-1]+v);
}
// 3번 칸이 아닐 경우
if(j+1 < 3){
tmp1 = max(tmp1,big[j+1]+v);
tmp2 = min(tmp2,small[j+1]+v);
}
// 해당 임시 dp 배열에 값 넣음
btmp[j] = tmp1;
stmp[j] = tmp2;
}
}
// 진짜 dp 배열에 임시로 저장해뒀던 dp배열로 값 덮어씌움
for(int k = 0; k < 3; k++){
big[k] = btmp[k];
small[k] = stmp[k];
}
}
int bigAns = 0;
int smallAns = 9999999;
// 1,2,3열 중 제일 큰 거, 작은 것을 찾음
for(int i = 0; i < 3; i++){
bigAns = max(bigAns,big[i]);
smallAns = min(smallAns,small[i]);
}
cout << bigAns << "\n" << smallAns;
}코드 상으로는 그렇게 어려운 것은 없다.
체크해줘야 하는 것은 1번 칸과 3번 칸 일 때
인덱스 밖으로 나가지 않도록 예외처리를 잘해주는 것이다.
그 외에는 임시 배열인 tmp 관리를 잘해주는 것이 관건이다.
나머지는 주석을 통해 이해가 가능하기 때문에 설명은 여기에서 마치겠다.
시행착오
DP 접근은 금방 하고 점화식도 금방 세웠지만
메모리 초과 때문에 풀지 못했던 문제
DP에 슬라이딩 윈도 기법을 적용해 보는 것은 처음이었다.
아예 처음 해보는 것이라서 그런지 신선했다.
앞으로도 이런 유형의 문제를 많이 풀어보긴 해야겠다.
생활비..