[백준][C++]9465 - 스티커

문제

• 9465번 : 스티커
• Rank : Silver I
• https://www.acmicpc.net/problem/9465

9465번: 스티커

 

풀이 전략

• i번째 줄의 스티커를 뗄 때, 경우의 수는 다음과 같이 나타낼 수 있다
  • i-1번째 줄에서 스티커를 떼지 않음
  • i-1번째 줄에서 위쪽 줄 스티커를 뗌
  • i-1번째 줄에서 위쪽 줄 스티커를 떼지 않음.
• 그리고, i-1번쨰 줄에서 다음 상태였을때, i번째 줄의 각 상태로 이행할 수 있다.
  • i-1번째 줄에서 떼지 않음/위쪽을 뗌 -> 아래쪽을 뗄 수 있음
  • i-1번째 줄에서 뗴지 않음/아래쪽을 뗌 -> 위쪽을 뗄 수 있음
  • 모든 경우의 수 -> 떼지 않음
    • 하지만 i-1번째 줄에서 떼지 않은 경우의 스코어 < i-1번째 줄에서 위쪽/아래쪽을 뗀 경우의 스코어이기 때문에, 위쪽/아래쪽을 뗀 경우만만을 비교한다
• for루프를 사용하여 1~N번째 줄까지, 3가지 상태에 대하여 도출가능한 이전 상태 중 높은 값을 선택하는 식으로 계산을 이어나간다.

// 0 : 위쪽을 뗌
// 1 : 아래쪽을 뗌
// 2 : 떼지 않음
unsigned int stickerMap[100000][2];
unsigned int maxPoint[100000][3];

	for (int i = 1; i < N; i++)
	{
		//up
		if (maxPoint[i-1][1] > maxPoint[i-1][2])
		{
			maxPoint[i][0] = maxPoint[i - 1][1] + stickerMap[i][0];
		}
		else
			maxPoint[i][0] = maxPoint[i - 1][2] + stickerMap[i][0];
		//down
		if (maxPoint[i - 1][0] > maxPoint[i - 1][2])
		{
			maxPoint[i][1] = maxPoint[i - 1][0] + stickerMap[i][1];
		}
		else
			maxPoint[i][1] = maxPoint[i - 1][2] + stickerMap[i][1];
		//none
		if (maxPoint[i - 1][0] > maxPoint[i - 1][1])
			maxPoint[i][2] = maxPoint[i - 1][0];
		else
			maxPoint[i][2] = maxPoint[i - 1][1];
	}

• 계산이 끝난 후, maxPoint[N-1]의 0~2번째 값 중 큰 값을 리턴한다.

전체 소스 코드

#include <iostream>
#include <memory.h>
using namespace std;

unsigned int stickerMap[100000][2];
unsigned int maxPoint[100000][3];

int testCases = 0;
int N = 0;

void run()
{
	maxPoint[0][0] = stickerMap[0][0];
	maxPoint[0][1] = stickerMap[0][1];
	maxPoint[0][2] = 0;

	for (int i = 1; i < N; i++)
	{
		//up
		if (maxPoint[i-1][1] > maxPoint[i-1][2])
		{
			maxPoint[i][0] = maxPoint[i - 1][1] + stickerMap[i][0];
		}
		else
			maxPoint[i][0] = maxPoint[i - 1][2] + stickerMap[i][0];
		//down
		if (maxPoint[i - 1][0] > maxPoint[i - 1][2])
		{
			maxPoint[i][1] = maxPoint[i - 1][0] + stickerMap[i][1];
		}
		else
			maxPoint[i][1] = maxPoint[i - 1][2] + stickerMap[i][1];
		//none
		if (maxPoint[i - 1][0] > maxPoint[i - 1][1])
			maxPoint[i][2] = maxPoint[i - 1][0];
		else
			maxPoint[i][2] = maxPoint[i - 1][1];
	}

}

int main()
{
	int numb, temp;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> testCases;

	for (int i = 0; i < testCases; i++)
	{
		unsigned int tempMaxValue = 0;
		//input
		cin >> N;
		for (int j = 0; j < N; j++)
		{
			cin >> stickerMap[j][0];
		}
		for (int j = 0; j < N; j++)
		{
			cin >> stickerMap[j][1];
		}
		//run
		run();

		for(int j = 0; j < 3; j++)
		{
			if (tempMaxValue < maxPoint[N-1][j])
				tempMaxValue = maxPoint[N-1][j];
		}
		cout << tempMaxValue << "\n";
	}
	return 0;
}

 

Note

• 이전 계산값을 사용하지 않기때문에, maxPoint를 배열 대신 변수 6개(current, next)로 사용하는 방법도 생각할만했다. 다만 그 경우 계산량이 부족하여, 문제의 메모리 제한(256MB)을 최대한 활용하는 방향으로 풀이했다.
• 입력을 받아오는 양이 많기때문에, sync_with_studio, cin.tie(NULL)을 사용하여 입력을 최적화해주지 않으면 시간제한에 걸린다.