9465 스티커

풀이코드

#include <iostream>
#include <cstdio>
using namespace std;
#define MAX 100000
// 9465

int max(int a, int b) {return a > b ? a : b;}
int max(int a, int b, int c){
	return max(a, b) < c ? c : max(a, b);
}

int main(){
	int T, width, board[MAX + 1][2], dp[MAX + 1][3];
	int result[100] = {0};
	
	cin >> T;
	cin.ignore();
	
	for(int t = 0; t < T; t++){
		cin >> width;
		cin.ignore();
		for(int k = 0; k < 2; k++){
			for(int j = 1; j <= width; j++){
				cin >> board[j][k];
			}	
		}
		dp[1][0] = 0;
		dp[1][1] = board[1][0];
		dp[1][2] = board[1][1];
		for(int i = 2; i <= width; i++){
			// 1. 아무것도 떼지 않는다.
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]);
			// 2. 위 스티커를 뗀다.
			dp[i][1] = max(dp[i - 1][0], dp[i - 1][2])
						+ board[i][0];
			// 3. 아래 스티커를 뗀다.
			dp[i][2] = max(dp[i - 1][0], dp[i - 1][1])
						+ board[i][1];
		}
		result[t] = max(dp[width][0], dp[width][1], dp[width][2]);
	}
	for(int t = 0; t < T; t++){
		cout << result[t] << endl;
	}
}

 

해설

처음 문제를 보고 잘못된 접근을 하였었다. 바로, 지그재그 형태의 두 개 답 만을 비교하여 최댓값을 도출해내겠다는 생각이었는데, 첫번 째 테스트 케이스로 인해서 내 망상은 바로 무너졌다.

다음으로 해답을 찾은 것이 DP 를 이용한 점화식 생각해보기 였다. 한 열에서는 3가지의 동작을 취할 수 있다.

1. 아무것도 떼지 않는다. => 이전 열에서의 3 가지 선택 중 max 를 갖는다

2. 위 스티커를 뗀다. => 이전 열에서의 1번 행동과 3번 행동 중 max 를 찾고 위 스티커를 더한다

3. 아래 스티커를 뗀다. => 이전 열에서의 1번 행동과 2번 행동 중 max 를 찾고 아래 스티커를 더한다

로직을 짜는 것은 쉬웠으나 결국 시간을 잡아먹었던 것은 상수 오타이다. 배열의 시작을 1로 하기로 해놓고서는 코딩을 하다가 보면 0으로 시작하는 자가당착에 빠졌었다. 

내가 구현한 로직에 이상이 없는데 오류가 난다면 상수 오타를 다시 한번 찾아보자 시간이 부족하기에

또한 이 문제를 풀어보며 느낀 점은, 모든 test case 에 대한 정보를 저장해 둘 필요가 없다는 점이었다. 각 테스트 케이스의 결과 값만을 저장해두고 나중에 출력하는 것이 메모리 상으로 훨씬 매우 절약이다.