C++) 백준 9465번 풀이_스티커

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

비쥬얼스튜디오에서는 큰 배열이 안 돌아가서 작게해서 코드짜다가 그대로 제출해서 나오는 런타임 에러.....

\n안넣어서 틀리기.... 개화남

 

 

무튼 와... 이거는... 뭐지? 왤케어려웠지? 일단 풀었다.

 

각 칸까지의 최대값을 구해보면 된다는 개념까지는 이제 이해를 해서 그 접근까지는 쉬웠는데

그 뒤가 어려웠다 ㅠ 

 

처음엔 각 칸의 왼쪽에서부터의 각 스티커까지의 최대값을 구해서 더했는데 시간초과가 떴다. 

어느 부분에서 시간초과가 나고 있는지 다시 확인했는데 내 로직상으로는 시간 초과가 날 곳이 없는거다..ㅠ

 

그래서 좀 찾아봤더니 불필요한 계산을 하고 있다는 것을 깨달았다.

 

진한 파란색 스티커를 뽑을 경우의 최대값을 구할 때,

주황색 스티커 두 위치까지의 최대값만 신경쓰면 된다는 사실을 알아내는게 중요했다.

 

파란색과 변을 공유하지 않는 스티커.. 세 칸 이상 떨어져있을 경우에는 중간에 스티커를 한장이라도 먹게 될테니 상관 없다고 생각해도, 왜 빨간색 위치까지의 최대값을 신경쓰지 않는가? 생각하느라 시간을 좀 잡아먹었는데

-> 생각해보면 빨간색부분을 뗄 경우 노란색 스티커를 떼낼 수 있기 때문에, 노란색 스티커까지의 최대값에 이미 들어가게 되어있었다.

 

 

 

같은 논리로

마지막 값을 고를 때

처음엔 주황색과 파란색 4칸 중의 max값을 구했는데

좀 더 생각해보니 같은 원리로 주황색 칸에 대한 고려가 필요없다는 사실을 깨달았다.

 

....

 

이제 이걸 코드로 짜면 됩니다.

 

	#include<stdio.h>
	#include<algorithm>
	using namespace std;
    
	int main(void) {
		int i, j, k, cnt, len ;
		int inp[2][100001] = { 0 };
		long long int sum[2][100001] = { 0 };

		scanf("%d", &cnt);

		for (i = 0; i < cnt; ++i)
		{
			scanf("%d", &len);
			for (j = 0; j < 2; ++j)
			{
				for (k = 1; k <= len; ++k)
				{
					scanf("%d", &inp[j][k]);
				}
			}

			sum[0][1] = inp[0][1];
			sum[1][1] = inp[1][1];

			for (j = 2; j <= len; ++j)
			{
				sum[0][j] = max(sum[1][j - 1], sum[1][j - 2]) + inp[0][j];
				sum[1][j] = max(sum[0][j - 1], sum[0][j - 2]) + inp[1][j];
			}
		
			long long int res = max(sum[0][len], sum[1][len]);
			printf("%lld\n", res);
		}
	}