[BOJ] 9465번 : 스티커

1. problem : 

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

 

 

2. solution 1 : 

#include <bits/stdc++.h>
using namespace std;
const int val = 100005;
int a[3][val];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t; 
	cin >> t; 
	while (t--) {
		int n; 
		int d[2][3][2] = { 0 };
		cin >> n; 
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= n; j++) cin >> a[i][j];
		}
		for (int i = 1; i <= n; i++) {
			d[i % 2][1][0] = max({ d[(i - 1) % 2][1][1],d[(i - 1) % 2][2][1] });
			d[i % 2][1][1] = max({ d[(i - 1) % 2][1][0] + a[1][i], d[(i - 1) % 2][2][1] + a[1][i] });
			d[i % 2][2][0] = max(d[(i - 1) % 2][1][1], d[(i - 1) % 2][2][1]);
			d[i % 2][2][1] = max({ d[(i - 1) % 2][1][1] + a[2][i], d[(i - 1) % 2][2][0] + a[2][i] });
		}
		cout << max({ d[n % 2][1][0],d[n % 2][1][1],d[n % 2][2][0],d[n % 2][2][1] }) << '\n';
	}
}

dp를 이용해 풀었다. 따라서, 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d [i][j][k] --> i번째 열, j번째 행을 k== 1은 선택했을 때의 최댓값이다. k == 0은 선택하지 않았을 때의 최댓값이다. 

2. 점화식을 작성한다. d [i][1][0], d [i][1][1], d [i][2][0], d [i][2][1]을 작성하면 된다. 이때, 점화식은 위에 있는 코드를 참고한다. 

3. 초기값을 설정한다. d [0]~를 0으로 초기화하면 된다. 

 

★ 나는 이번에 문제를 풀 때, d라는 배열을 [val][3][3]으로 두어, stack 메모리를 너무 많이 쓴다는 warning message를 받았다. 따라서, i % 2를 이용해 이전값과 현재값만을 사용하는 방식으로 바꿔야 했다.(chatGPT가 이런 방법을 알려주었다.) 

 

 

 3. solution 2 : 

// Authored by : heheHwang
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/11776ce32bae48799ae66340d730cfd4
#include <bits/stdc++.h>
using namespace std;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int tc;
  cin >> tc;
  while (tc--) {
    int N;
    cin >> N;
    vector<vector<int>> arr(N, vector<int>(2)), dp(N, vector<int>(2)); // N by 2 vector를 선언
    for (int j = 0; j < 2; j++)
      for (int i = 0; i < N; i++)
        cin >> arr[i][j];
    
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < 2; j++) {
        int v = 0;
        if (i > 1) v = max(dp[i - 2][0], dp[i - 2][1]);
        if (i > 0) v = max(v, dp[i - 1][1 - j]);
        dp[i][j] = v + arr[i][j];
      }
    }
    cout << max(dp[N - 1][0], dp[N - 1][1]) << '\n';
  }
}

/*
dp[i][j] : i번째 열까지에서 점수의 최댓값, 단 j행 i열의 스티커는 반드시 선택

가장 직전에 붙인 스티커가 i-2열의 스티커인 경우 : max(dp[i - 2][0], dp[i - 2][1]) + arr[i][j]
가장 직전에 붙인 스티커가 i-1열의 스티커인 경우 : dp[i-1][1-j] + arr[i][j]

마지막 열에 있는 스티커 중 어느 하나는 반드시 붙인게 최댓값이므로 max(dp[N - 1][0], dp[N - 1][1])을 계산하면 됨
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/9465.cpp

basic-algo-lecture/0x10/solutions/9465.cpp at master · encrypted-def/basic-algo-lecture

테이블을 2차원으로 정의했다. 또한, vector를 이용했다. 그리고 i > 1 , i > 0일 때 두 번의 검사를 통해 테이블의 값을 채운다. 아직 완벽히 이해가 가지 않는다. 다음에는 이 방법으로 풀어봐야겠다.