[백준] 9463번. 스티커 (C++)

문제 설명

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

9465번: 스티커

 

해결 방향

DP문제이다.

 

#include<iostream>
using namespace std;


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


void stickerCalculate() {
	
	int N;
	cin >> N;

	int score[2][100001];
	int arr[2][100001];


	for (int i = 0; i < 2; i++)
	{
		for (int j = 1; j <= N; j++) { cin >> score[i][j]; }
	}


	arr[0][0] = 0;
	arr[1][0] = 0;

	arr[0][1] = score[0][1];
	arr[1][1] = score[1][1];


	for (int i = 2; i <= N; i++)
	{
		arr[0][i] = max(arr[1][i - 1], arr[1][i - 2]) + score[0][i];
		arr[1][i] = max(arr[0][i - 1], arr[0][i - 2]) + score[1][i];
	}

	cout << max(arr[0][N], arr[1][N])<<"\n";

}



int main() {

	int T;
	cin >> T;

	for (int i = 0; i < T; i++){ stickerCalculate(); }

}

 

int score[2][100001];
int arr[2][100001];

score - 스티커 점수 배열

arr - dp배열. 최댓값을 찾기위해 계산한 값들 저장하는 배열

 

 

 

 

 

예를 들자면 다음과 같다.

score에 점수를 입력받고 arr에서 점수를 계산한다.

합이 최대이고 찢어지지 않는 스키터를 얻기 위해서는

지그재그로 스티커를 선택해야 한다.

대각선 위치에 있는 수를 선택하는 것이다. 

 

 

예를들어 230+50칸은

대각선에 있는 20+20, 140+90 중에 140+90 이 더 큰 수이므로 50에 230을 더해준 것이다.

 

그렇다면 여기서 의문이 생긴다.

첫번째 대각선 자리의 숫자 40과 두번째 대각선 자리의 숫자 230을 비교했다면

세번째 네번째 다섯번째 등... 모든 대각선 자리에 있는 수를 확인해야하는 것인가 하는 의문말이다.

 

정답은 아니다.

세번째 부터는 하나씩 대각선으로 더하는것이 무조건적으로 크기 때문에

우리는 첫번째 두번째 대각선만 확인하면 된다.

예를 들자면 다음과 같다.

따라서 우리는 두가지 대각선 자리에 있는 수만 확인하면 된다.

 

 

 

 

 

for (int i = 0; i < 2; i++)
{for (int j = 1; j <= N; j++) { cin >> score[i][j]; }}
스티커 점수를 입력받는다.

 

 

arr[0][0] = 0;
arr[1][0] = 0;

arr[0][1] = score[0][1];
arr[1][1] = score[1][1];

 

for (int i = 2; i <= N; i++)
{
arr[0][i] = max(arr[1][i - 1], arr[1][i - 2]) + score[0][i];
arr[1][i] = max(arr[0][i - 1], arr[0][i - 2]) + score[1][i];
}

첫번째 대각선 자리 arr[1][i-1] 두번째 대각선 자리 arr[1][i-2]수 중에 더 큰 숫자를

자신과 같은 자리의 점수 score[0][i]에 더한다.

 

첫번째 줄 두번째 줄을 둘다 계산해준다.

 

cout << max(arr[0][N], arr[1][N])<<"\n";

최종으로 더 큰 숫자를 출력한다.