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

풀이

#include <iostream>
#define max(a,b) (((a)>(b))?(a):(b))
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {	// 테스트 케이스만큼 반복
	int n;
	cin >> n;
	int a[100001][2], d[100001][3];	// 배열 크기 할당
	for (int i=1; i<=n; i++) cin >> a[i][0];
	for (int i=1; i<=n; i++) cin >> a[i][1];
	d[0][0] = d[0][1] = d[0][2] = 0;
	for (int i=1; i<=n; i++) {
		d[i][0]=max(d[i-1][0],max(d[i-1][1],d[i-1][2]));	// 각 배열에 해당하는 계산
		d[i][1]=max(d[i-1][0],d[i-1][2]) + a[i][0];
		d[i][2]=max(d[i-1][0],d[i-1][1]) + a[i][1];
	}
	long long ans = 0;
    ans = max(d[n][0],max(d[n][1],d[n][2]));	// 최댓값을 출력
    cout << ans << '\n';
    }
	return 0;
}

개념

다이나믹 프로그래밍 문제이다. 

복잡하고 어려워서, 더이상 다이나믹 문제 같지가 않다..

추가적인 개념으로는, 앞에서 정의한 max(a,b)함수를 사용할 때 3개의 인자를 비교하고 싶으면 max( a, max(b, c) ) 이런식으로 사용하면 된다.

---

풀이 

입력 값에 해당하는 여러 값들을 저장하기 위해 이차원 배열을 사용해야한다.

a배열을 그 용도로 사용하고, d배열은 최댓값들을 저장하기 위해 사용한다.

다양한 최댓값이 나타나는데, n이 증가하고 새로운 값이 추가됨에 따라 이전 최댓값을 사용하지 않을 수도 있다.

따라서 여러개의 최댓값 빌드를 사용해야한다.

문제는 크게 3개로 나눌 수 있다.

 

①n의 2개 값 모두 고르지 않을 때

-> n-1 값에서  ①,②,③ 모두가능하다

②n의 첫번째 값 고를 때

-> n-1 값에서  ①,③ 가능하다

③n의 두번째 값 고를 때

-> n-1 값에서  ①,② 가능하다

 

이 중 가장 큰 값이 다음으로 이동되므로 최댓값을 대입한다.

값들을 더해주기 위해 다음과 같이 표현한다.

 

d[i][0]=max(d[i-1][0],max(d[i-1][1],d[i-1][2])); 
d[i][1]=max(d[i-1][0],d[i-1][2]) + a[i][0];
d[i][2]=max(d[i-1][0],d[i-1][1]) + a[i][1];

 

---

+a

이 문제에서 long long을 쓰는 풀이를 봤는데, int 자료형을 써도 문제 없이 구현이 된다.

그리고 다음과 같은 추가적 계산이 있던데, 이를 사용하지 않아도 구현이 된다.

	long long ans = 0;
        for (int i=1; i<=n; i++) {
            ans = max(max(ans,d[i][0]),max(d[i][1],d[i][2]));
        }
	cout << ans << '\n';

만일 이 문제가 n-1 상태가 n보다 더 큰 값을 가질 수 있다면 이러한 계산을 적어야한다.

하지만 아무리 적은 값이어도 n-1에서 n이 되며 증가하므로 필요없는 계산이라고 생각된다.

 

※풀어야할 다이나믹 프로그래밍 문제가 많은데, 지금 레벨로는 감당이 안되는 것 같다..

다른 유형의 문제를 풀고 다시 접근할 계획이다.