-
[Baekjoon Online Judge] 9465번: 스티커문제 풀이/Baekjoon Online Judge 2021. 3. 4. 11:52
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
요구사항
- 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.
- 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.
입력
- 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다.
- 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
- 각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.
50 10 100 20 40 30 50 70 10 60 각 스티커가 가진 가중치가 위와 같다고 가정한다.
1, 1은 50의 값을 가장 크게 가져올 수 있다.
2, 1은 30의 값을 가장 크게 가져올 수 있다.
1, 2은 30 + 10인 40이 가장 큰 값으로 가져올 수 있다.
2, 2는 50 + 50으로 100을 가장 큰 값으로 가져올 수 있다.
1, 3은 총 3가지의 수를 비교할 수 있다. 1, 1과 1, 2, 그리고 2, 2의 값 까지의 집합 중 가장 큰 값을 자신과 더해주어 집합에 포함시킨다.
이것을 dp 테이블에 적용해보았다.
50 30 + 10 50 + 100 vs 30 + 100 vs 50 + 50 + 100 ... ... 30 50 + 50 50 + 70 vs 30 + 70 vs 30 + 10 + 70 ... ... 50 40 200 140 250 30 100 120 210 260 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Baekjoon9465 { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(bufferedReader.readLine()); // 테스트 케이스의 개수 T for (int i = 0; i < t; i++) { int n = Integer.parseInt(bufferedReader.readLine()); // n int[][] stickers = new int[2][n]; int[][] dp = new int[2][n]; String[] input = bufferedReader.readLine().split(" "); for (int j = 0; j < n; j++) stickers[0][j] = Integer.parseInt(input[j]); input = bufferedReader.readLine().split(" "); for (int j = 0; j < n; j++) stickers[1][j] = Integer.parseInt(input[j]); for (int j = 0; j < n; j++) { if (j == 0) { dp[0][j] = stickers[0][j]; dp[1][j] = stickers[1][j]; } else if (j == 1) { dp[0][j] = stickers[0][j] + dp[1][j - 1]; dp[1][j] = stickers[1][j] + dp[0][j - 1]; } else { dp[0][j] = Math.max( Math.max(stickers[0][j] + dp[0][j - 2], stickers[0][j] + dp[1][j - 2]), stickers[0][j] + dp[1][j - 1]); dp[1][j] = Math.max( Math.max(stickers[1][j] + dp[0][j - 2], stickers[1][j] + dp[1][j - 2]), stickers[1][j] + dp[0][j - 1]); } } System.out.println(Math.max(dp[0][n - 1], dp[1][n - 1])); } bufferedReader.close(); } }
'문제 풀이 > Baekjoon Online Judge' 카테고리의 다른 글
[Baekjoon Online Judge] 11057번: 오르막 수 (0) 2021.03.08 [Baekjoon Online Judge] 1010번: 다리 놓기 (0) 2021.03.05 [Baekjoon Online Judge] 1934번: 요세푸스 문제 (0) 2021.03.04 [Baekjoon Online Judge] 11052번: 카드 구매하기 (0) 2021.02.26 [Baekjoon Online Judge] 10816번: 숫자 카드 2 (0) 2021.02.26