문제
https://www.acmicpc.net/problem/9465
풀이
2행 n열로 배치된 스티커를 떼서 얻을 수 있는 점수의 최댓값을 구하는 문제이다.
일단 2문제에서 떼고 안떼보고 전체적인 완탐을 수행하면 2^100000이기 때문에 무조건 시간초과가 난다.
그러면 이 문제를 어떻게 해결할 수 있을까?
결국 10만개의 데이터가 있다는 것은 선형적인 시간복잡도를 가지는 것으로 해결해야한다.
다이나믹 프로그래밍을 이용한다.
이전 열까지 스티커를 떼고 최댓값을 누적시키면서 갱신해보는 것이다.
만약에 이런 형태가 있다고 하자.(O: 뗀 스티커, X: 떼지 않은 스티커)
XXO
XXX
그러면 하단의 2가지가 된다. (?는 스티커가 붙여있는지 안붙여있는지 모른다는 의미이다.)
?XO
OXX
?XO
XOX
즉 밑에 있는 행에서 현재 열에서 -1, -2를 한 열의 최댓값에서(arr[1][i - 1], arr[1][i - 2]) 현재 위치의 스티커 값을 더하면 뗀 스티커의 최댓값이 되는 것이다.
그러면 ?위치에 있는 것은 왜 최댓값을 고려하지 않을까?
4개의 열을 그려보면 정답을 알 수 있다.(C는 현재 열이다)
OXXC
XXOC
XOXC
XXOC
?위치를 고려하지 않은 이유는 이미 이전 열에서 최댓값을 ?자리와 비교해서 갱신이 되었기 때문이다.
?XO
XOX
즉 이 경우에서 이미 최댓값이 갱신되었다. 그러므로 고려하지 않아도 된다.
1. 테이블을 정의한다.
dp[i][j] = i행, j열에서 뗄 수 있는 스티커의 최대 점수
2. 우리가 원하는 답을 구할 수 있는지 생각해본다.
결국 우리가 원하는 답은 j열에 있는 최대 점수들 중 최댓값을 구하면 된다.
3. 정의한 테이블을 어떻게 초기화할 것인지 생각해본다.
첫번째 열인 경우, 무조건 자신의 점수가 최댓값이 된다.
dp[0][1] = scores[0][1]
dp[1][1] = scores[1][1]
4. 점화식을 정의한다.
i >= 2일때,
dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + 현재 위치 점수
dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + 현재 위치 점수
소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringTokenizer st = null;
StringBuilder sb = new StringBuilder();
while (t > 0) {
int n = Integer.parseInt(br.readLine());
int[][] scores = new int[2][n + 1];
int[][] dp = new int[2][n + 1];
for (int i = 0; i < 2; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 1; j <= n; j++) {
scores[i][j] = Integer.parseInt(st.nextToken());
}
}
dp[0][1] = scores[0][1];
dp[1][1] = scores[1][1];
for (int i = 2; i <= n; i++) {
dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + scores[0][i];
dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + scores[1][i];
}
sb.append(Math.max(dp[0][n], dp[1][n])).append("\n");
t--;
}
System.out.print(sb);
br.close();
}
}
실행결과

'Problem Solving > Baekjoon' 카테고리의 다른 글
| [Baekjoon] 트리 - Java (0) | 2025.09.11 |
|---|---|
| [Baekjoon] 텀 프로젝트 - Java (0) | 2025.09.10 |
| [Baekjoon] LCS2 - Java (0) | 2025.09.08 |
| [Baekjoon] LCS - Java (0) | 2025.09.06 |
| [Baekjoon] DSLR - Java (0) | 2025.09.04 |