개요

[링크]백준 9465번: 스티커

• 입력
  첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

• 출력
  각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

접근 방식

• 처음 방식(실패)
  바텀업으로 구현을 시도했다.
  하지만 아직 잘 안 잡힌 개념이다 보니
  dp[i+1][1] += dp[i][2] + inputArr[0][i];
  dp[i + 1][2] += dp[i][1] + inputArr[1][i];
  이런 식으로 그냥 위 스티커를 고른 상태라면 아래 스티커 고르고 ,
  아래 스티커를 고른 상태라면 위 스티커 고르는 식으로 더해나갔다.
  당연하지만 이런 식으로 쌓아올리면 모든 최대값들을 비교가 불가능하고 답을 낼 수 없었다.

• 두번째 방식
  마찬가지로 바텀업 방식이지만
  dp배열에 0,1,2로 나눠서 전에 아무것도 안 골랐을때,
  위에 골랐을 때, 아래를 골랐을 때 이렇게 세가지로 나눠서 최대값을 넣어주고 쌓아올린 뒤, 마지막에 0일때,1일때,2일때 비교해서 최대값을 출력하는 방식

• 세번째 방식
  재귀를 이용한 solution(current,before,amountArr) 함수이다.
  current열에서 시작해서 amountArr열까지 계산했을 때
  최댓값을 반환하는 함수이다.
  before이 0이면 current-1열에서 아무것도 안 뗀 경우,
  1이면 current-1열에서 위에 스티커를 뗀 경우,
  2면 current-1열에서 아래 스티커를 뗀 경우이다.

  예를 들어 solution(0,0,10)이라면
  solution(1,0,10), solution(1,1,10)+0번째 열의 위 스티커,
  solution(1,2,10)+0번째 열의 아래 스티커
  이 세가지 값에서 최대값을 구하는 방식이다.

두번째 방식 코드(반복문)

#include<iostream>										//3
//dp배열
int inputArr[2][100'001], dp[100'001][3], Ans = 0;
using namespace std;

void solution(int& amountArr);

//초기화 하는 함수
void initDp(int& amountArr) {
	for (int i = 0; i < amountArr; i++) {
		inputArr[0][i] = inputArr[1][i] = 0;
	}
	for (int i = 0; i < amountArr; i++) {
		dp[i][0] = dp[i][1] = dp[i][2] = 0;
	}
}

void input() {
	int amount = 0, amountArr = 0;
	cin >> amount;
	for (int i = 0; i < amount; i++) {
		cin >> amountArr;
		for (int j = 0; j < amountArr; j++) {
			cin >> inputArr[0][j];
		}
		for (int j = 0; j < amountArr; j++) {
			cin >> inputArr[1][j];
		}
		solution(amountArr);
		initDp(amountArr);
	}

}

//바텀업방식으로 쌓아올리는 함수
void solution(int& amountArr) {

	for (int i = 0; i < amountArr; i++) {
        //i+1번째 열에서, 0일 때(i번째 열에서 아무것도 안 더했을 때) 최댓값
        //-> i번째 열에서, (0,1,2)인 세 값 중 최대값 저장
		dp[i+1][0] = max(dp[i][0],max(dp[i][2],dp[i][1]) );
        //i+1번째 열에서, 1일 때(i번째 열에서 위 스티커를 더했을 때) 최댓값
        //-> i번째 열에서, 0일 때와 2일때 중 더 큰값에 위 스티커값 더해준후 저장
		dp[i+1][1] = max(dp[i][2],dp[i][0]) + inputArr[0][i];
        //i+1번째 열에서, 2일 때(i번째 열에서 위 스티커를 더했을 때) 최댓값
        //-> i번째 열에서, 0일 때와 1일때 중 더 큰값에 아래 스티커값 더해준후 저장
		dp[i+1][2] = max(dp[i][1],dp[i][0]) + inputArr[1][i];
	}
    //최종적으로 0,1,2 중 제일 큰 값 답으로 출력
	int ans = max(dp[amountArr ][0], max(dp[amountArr ][1], dp[amountArr][2]));
	cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	input();
}

세번째 방식 코드(재귀)

#include<iostream>

using namespace std;

int inputArr[2][100'001], dp[100'001][3], Ans = 0;

int solution(int current, int before,int amountArr);

void initDp(int& amountArr) {
	for (int i = 0; i < amountArr; i++) {
		dp[i][0] = dp[i][1] = dp[i][2] = -1;
	}
}

void input() {
	int amount = 0, amountArr = 0;
	cin >> amount;
	for (int i = 0; i < amount; i++) {
		cin >> amountArr;
		for (int j = 0; j < amountArr; j++) {
			cin >> inputArr[0][j];
		}
		for (int j = 0; j < amountArr; j++) {
			cin >> inputArr[1][j];
		}
		//dp 초기화
		initDp(amountArr);
		cout<<solution(0,0,amountArr)<<'\n';
	}
}
//current열부터 땠을 때 최대값, before이 0이면 current-1열에서 아무것도 안 뗀 것, 1이면 윗값 뗀 것, 2이면 아랫값 뗀 것 
int solution(int current, int before, int amountArr) {
	//current열이 최종값에 다다르면 return 0 해주기
	if (current == amountArr) return 0;
	//배열에 저장해놔서 다시 계산 안하도록
	if (dp[current][before] != -1) return dp[current][before];
	//ans는 before이 0일 때로 초기화
	int ans = solution(current + 1, 0, amountArr);

	//만약 before이 0이나 2라면
	if (before != 1) {
		//c+1열에서 before이 0일 때와, before이 2일 때 비교 해서 더 큰 값 저장
		ans = max(ans, solution(current + 1, 1, amountArr) + inputArr[0][current]);
	}
	//만약 before이 0이나 1이라면
	if (before != 2) {
		//c+1열에서 before이 0이거나 1일때 비교해서 더 큰 값 저장
		ans = max(ans, solution(current + 1, 2, amountArr) + inputArr[1][current]);
	}
	//dp배열에 저장해놓기
	dp[current][before] = ans;
	//ans return
	return ans;
}


int main() {
	input();
}

문풀후생

재귀방식이 안 와닿아서 공책에 호출이 되는 경로 적어보며
공부했던 문제다.
좀 더 다양한 문제들을 풀어보며 익숙해져야겠다.