백준 9465번 [스티커](C++) -yes6686- 티스토리

백준 문제 풀이: 9465 [스티커]

---

문제 링크: https://www.acmicpc.net/problem/9465

문제 설명:

두 줄로 구성된 스티커에서 스티커를 선택해 최대 점수를 얻는 문제입니다. 다음 조건이 적용됩니다:

• 한 열에서 두 개의 스티커 중 하나만 선택할 수 있습니다.
• 인접한 열에서 선택한 스티커와 같은 행의 스티커를 선택할 수 없습니다.
• 점수의 합이 최대가 되는 값을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[3][100001]; // 스티커 점수를 저장하는 배열
int dp[3][100001];  // 최대 점수를 저장하는 DP 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T; // 테스트 케이스 수
    cin >> T;

    while (T--) {
        int n; // 열의 개수
        cin >> n;

        // 스티커 점수 입력
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> arr[i][j];
            }
        }

        // 초기값 설정
        dp[1][1] = arr[1][1];
        dp[2][1] = arr[2][1];

        if (n > 1) {
            dp[1][2] = arr[1][2] + arr[2][1];
            dp[2][2] = arr[2][2] + arr[1][1];
        }

        // DP 계산
        for (int i = 3; i <= n; i++) {
            dp[1][i] = max(dp[2][i - 1], dp[2][i - 2]) + arr[1][i];
            dp[2][i] = max(dp[1][i - 1], dp[1][i - 2]) + arr[2][i];
        }

        // 결과 출력
        cout << max(dp[1][n], dp[2][n]) << '\n';
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 현재 열의 스티커를 선택했을 때의 최대 점수를 계산합니다. 스티커 선택 조건에 따라 이전 열의 최댓값을 활용합니다.
• 구현 세부사항:
  • dp[1][i]: 1행 i열 스티커를 선택했을 때의 최대 점수
  • dp[2][i]: 2행 i열 스티커를 선택했을 때의 최대 점수
  • 점화식:
    • dp[1][i] = max(dp[2][i-1], dp[2][i-2]) + arr[1][i]
    • dp[2][i] = max(dp[1][i-1], dp[1][i-2]) + arr[2][i]
• 시간 복잡도 분석: O(n) (테스트 케이스 T에 대해 총 O(T × n))
  • 각 열을 순회하며 최대 점수를 계산합니다.

---

결과

주어진 스티커 배열에서 조건을 만족하며 얻을 수 있는 최대 점수를 효율적으로 계산합니다. DP 배열을 통해 중복 계산을 줄이고, 테스트 케이스마다 독립적으로 수행됩니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!