[알고리즘] 스티커

구현 방식

• 동적계획법을 사용한다.
• 배열 acc를 다음과 같이 정의한다. 스티커는 i 열에 0번째 , 1번째 로 총 두개의 스티커가 있다.

acc[0][i] // i 열 0 번째 스티커를 떼어냈을 때의 최대값
acc[1][i] // i 열 1 번째 스티커를 떼어냈을 때의 최대값
acc[2][i] // i 열의 스티커를 한개도 떼지 않았을 때의 최대값

• acc가 다음과 같을 때 아래와 같은 점화식을 세울 수 있다.

// 바로 이전 직전의 누적값에서 1번째 스티커를 떼어냈을 때와 아무것도 안떼어냈을 때와 비교 (바로 직전 누적값 중 0번째 스티커를 떼어낸건 변을 마주하므로 불가)
acc[0][i] = max(acc[1][i - 1] + weight[0][i], acc[2][i - 1] + weight[0][i])
// 바로 이전 직전의 누적값에서 0번째 스티커를 떼어냈을 때와 아무것도 안떼어냈을 때와 비교 (바로 직전 누적값 중 1번째 스티커를 떼어낸건 변을 마주하므로 불가)
acc[1][i] = max(acc[0][i - 1] + weight[1][i], acc[2][i - 1] + weight[1][i])
// 아무것도 안떼어내므로, 바로 직전의 모든 값과 비교
acc[2][i] = max(acc[0][i - 1],acc[1][i - 1], acc[2][i - 1])

코드

• 최종 코드는 아래와 같다.

const int MAXSIZE = 100000;
int weight[2][MAXSIZE] = {};
int acc[3][MAXSIZE] = {};

void solution(int N)
{
	dp(N);

	int result = 0;
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < N; j++)
			result = max(acc[i][j], result);
	}

	cout << result << "\n";
}

void dp(int N)
{
	acc[0][0] = weight[0][0];
	acc[1][0] = weight[1][0];
	acc[2][0] = 0;

	for (int i = 1; i < N; i++)
	{
		acc[0][i] = max(acc[1][i - 1] + weight[0][i], acc[2][i - 1] + weight[0][i]);
		acc[1][i] = max(acc[0][i - 1] + weight[1][i], acc[2][i - 1] + weight[1][i]);
		for (int j = 0; j < 3; j++)
			acc[2][i] = max(acc[2][i], acc[j][i - 1]);

	}

}