[백준] 9465번 - 스티커 풀이 및 코드 분석 (Java)

문제 링크

---

1. 문제 분석

🏆 문제 개요

• 2 × n 크기의 스티커 배열에서 점수를 최대로 얻도록 스티커를 선택해야 한다.
• 단, 선택한 스티커와 변을 공유하는 스티커는 사용할 수 없다.
• 최대 점수를 출력하는 프로그램을 작성해야 한다.

🎯 요구사항

1. 각 테스트 케이스에 대해 최대 점수를 출력해야 한다.
2. 두 행(2 × n)으로 구성된 스티커 배열에서 인접하지 않은 스티커들을 선택해야 한다.
3. 1 ≤ n ≤ 100,000이므로, 효율적인 알고리즘이 필요하다. (시간 복잡도 O(n) 이하)

---

2. 해결 방법

🔹 핵심 개념

이 문제는 다이나믹 프로그래밍(DP)을 활용하면 효과적으로 해결할 수 있다.
점화식을 세우는 것이 핵심이며, 각 위치에서 얻을 수 있는 최대 점수를 누적해 나가는 방식이다.

🔑 해결 절차

1. 입력값 처리 및 DP 테이블 초기화
   • sticker[2][n] 배열을 입력받아 스티커 점수를 저장한다.
   • dp[2][n] 배열을 사용하여 해당 위치까지의 최대 점수를 저장한다.
2. DP 점화식 세우기
   • 기본 아이디어: dp[i][j] = max(이전 행의 선택 가능 칸 + 현재 칸 점수)
   • dp[0][j] = max(dp[1][j-1], dp[1][j-2]) + sticker[0][j]
   • dp[1][j] = max(dp[0][j-1], dp[0][j-2]) + sticker[1][j]
3. 최종 출력
   • Math.max(dp[0][n-1], dp[1][n-1]) 값 출력.

---

3. 코드 구현

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine()); // 스티커 개수
            int[][] sticker = new int[2][n];
            int[][] dp = new int[2][n];

            // 스티커 점수 입력
            StringTokenizer st;
            for (int i = 0; i < 2; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    sticker[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // DP 초기값 설정
            dp[0][0] = sticker[0][0];
            dp[1][0] = sticker[1][0];

            if (n > 1) {
                dp[0][1] = sticker[1][0] + sticker[0][1];
                dp[1][1] = sticker[0][0] + sticker[1][1];
            }

            // DP 점화식 적용
            for (int j = 2; j < n; j++) {
                dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + sticker[0][j];
                dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + sticker[1][j];
            }

            // 최대 점수 출력
            System.out.println(Math.max(dp[0][n-1], dp[1][n-1]));
        }
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. 입력 처리 & 초기화
   • sticker[2][n] 배열에 점수 입력
   • dp[2][n] 배열을 생성하여 각 칸까지의 최대 점수 저장
2. DP 점화식 적용
   • 초기값 설정 (dp[0][0], dp[1][0], dp[0][1], dp[1][1])
   • j ≥ 2부터 점화식을 적용하여 최대 점수를 누적 계산
3. 최종 출력
   • dp[0][n-1]과 dp[1][n-1] 중 큰 값 출력

🔹 시간 복잡도 분석

• 입력 처리: O(n)
• DP 연산: O(n)
• 총 시간 복잡도: O(n)
  • n ≤ 100,000이므로 충분히 빠르게 동작한다.

---

5. 개선할 점 및 대체 방법

✅ 개선할 점

1. 1차원 배열로 공간 최적화 가능
   • dp[0][j], dp[1][j] 값만 필요하므로, 크기를 dp[2][3]로 줄일 수 있다.
   • dp[0] = {prev1, prev2, cur} 형태로 저장하면 공간을 절약할 수 있다.
2. 입력과 동시에 DP 계산 가능
   • 별도의 dp[][] 배열을 만들지 않고, sticker[][]를 직접 수정하면서 DP 연산을 수행하면 메모리를 절약할 수 있다.

🔄 대체 방법

1. 배열 없이 변수만으로 DP 연산 가능
   • prev2, prev1, cur 변수를 사용하면 O(1) 공간 복잡도로 최적화 가능하다.
2. 탑다운(Top-Down) 방식의 재귀 + 메모이제이션
   • 현재 코드보다 더 복잡해지지만, 문제의 특성상 가능하다.

---

6. 결론

이 문제는 DP(다이나믹 프로그래밍)를 활용하여 최적의 스티커 선택을 찾는 문제이다.
💡 핵심은 이전 선택지와의 관계를 파악하고, 점화식을 적용하여 최댓값을 갱신하는 것!
DP 문제 유형을 연습하기에 적합하며, 공간 최적화 기법을 고민해볼 수도 있는 문제다. 🚀