스트릭 끊기는 거 보기 싫어서 엄청 바쁜 거 아니면 알고리즘 문제를 하루에 하나는 풀려고 하고 있다... 근데 지금까지 기계적으로 풀기만 하고 내가 무슨 문제를 풀었는지, 어떻게 접근해서 풀었는지 기록이 없으니까 남는 게 없는 거 같아서 이렇게 블로그를 쓰기로 다짐함.
마침 저번주에 알튜비튜에서 dp를 배웠기 때문에, 이 문제를 보자마자 매우매우 반가웠다. 정말 앞구르기 뒷구르기 백덤블링 다 하면서 봐도 dp인 문제!
(이유를 적자면, dp로 접근하기 위해서는 이전의 결과가 차곡차곡 쌓여서 다음의 결과로 넘어가는 형태를 하고 있어야 한다. 수학적 귀납법으로 증명하는 것처럼? 이 문제도 전 칸, 전전 칸의 결과를 가지고 원하는 칸의 결과를 구하기 때문에, 바로 dp를 떠올릴 수 있다.)
(순간 그래프 탐색으로 푸는 것도 잠시 생각했는데, 아무래도 이 문제는 두 칸을 띄우는 경우도 최대가 될 수 있어서 아마 힘들 듯?)
거기에 주어지는 스티커 배열의 형태도 2xn 형태로 고정되어 있기 때문에, 점화식을 세우는 것이 아주 간단했다. 거의 날먹했달까.... ㅎㅎ
그래서 사고 과정을 정리해보자면
1. 위의 이유로 dp 문제임을 깨달음.
2. 점수의 합을 저장하는 배열을 진행 순서와, 마지막으로 붙인 스티커의 방향으로 나뉜 2차 배열로 만들어야겠다는 생각을 함.
3. 스티커를 사용할 수 있는 경우를 조건을 보면서 생각함.
근데 사실 처음은 3번에서 스티커를 사용하는 경우가 그러면 w, m 형태로만 나오는 거 아닌가? 하고 두 칸 띄우는 경우를 전혀 생각을 못했음... 예제 보고 그럴 수 있겠네~ 하고 뒤늦게 깨달음.
그래서 원래는 w일 때, m일 때로 케이스를 나눠서 합을 구하려고 했는데, 바로 수정함. 정말 예제 덕분에 다시 고쳐서 생각할 수 있었지, 없었으면 아마 처음 생각한 대로 풀고 예제부터 틀렸을 듯ㅋㅋㅋㅋㅋ 이런 케이스도 떠올릴 수 있는 직관을 가지려고 노력하자..
값을 더하는 건 먼저 0, 1번 순서는 값을 지정해두고, 2번째부터는 마지막으로 사용한 스티커에 따라 최댓값을 배열에 집어넣음. 그 칸의 스코어 + max(전 칸 같은 줄의 누적 합, 전전 칸 같은 줄의 누적합) 이렇게 해서 최댓값을 구했음.
그리고 예제까지 돌려서 다 맞는 걸 보고 바로 제출을 했는데~ 틀렸다!
98퍼쯤에서 outofbounds가 떠서 왜 그럴까 생각을 했는데,
1. 거의 모든 케이스를 다 통과한 거니까 에러가 발생한 케이스는 아마 매우 예외적인 경우일 것.
2. outofbounds가 뜰 정도로 배열을 복잡하게 사용하지 않았음. 따라서 실수를 했을 가능성도 매우 적음.
이 모든 걸 종합해서, 0, 1번째 순서일 때 에러가 난다는 사실을 바로 파악함. 이건 좀 잘한 듯.ㅎㅎ
그래서 결과적으로 정답을 얻은 코드는 아래와 같다.
#include <iostream>
#include <vector>
using namespace std;
int dp (vector<vector<int>>& score, int n) {
//[순서][방향]
vector<vector<int>> score_sum (n, vector<int> (2, 0));
score_sum[0][0] = score[0][0];
score_sum[0][1] = score[1][0];
if (n == 1) return max(score_sum[n-1][0], score_sum[n-1][1]);
score_sum[1][0] = score_sum[0][1] + score[0][1];
score_sum[1][1] = score_sum[0][0] + score[1][1];
if (n == 2) return max(score_sum[n-1][0], score_sum[n-1][1]);
for (int i = 2; i < n; i++) {
score_sum[i][0] = score[0][i] + max(score_sum[i-2][1], score_sum[i-1][1]);
score_sum[i][1] = score[1][i] + max(score_sum[i-2][0], score_sum[i-1][0]);
}
return max(score_sum[n-1][0], score_sum[n-1][1]);
}
int main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
//[방향][순서]
vector<vector<int>> score (2, vector<int> (n, 0));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
cin >> score[i][j];
}
}
cout << dp(score, n) << '\n';
}
}score랑 score_sum 벡터 인덱스를 좀 헷갈리게 둬서 고생 좀 했음... 계산이 간단해서 망정이지 복잡했으면 틀렸을 듯ㅋㅋㅋ 좀 더 직관적으로 알아볼 수 있게 쓰려고 노력해야겠다
이렇게 오늘의 문제 끝~ 기본적인 dp를 복습할 수 있었던 좋은 문제였다~
