728x90
https://www.acmicpc.net/problem/9465
🤔 문제 접근
완전 탐색으로 풀려다가 실패한 문제이다.
스티커를 뗀 부분에서 맵을 벗어나지 않는 한도 안에 상하좌우에 있는 스티커가
같이 떼지는 형식이다.
이때 다음으로 고를 수 있는 스티커의 위치는 현재 뗀 위치의 행이 0인경우
sticker[1][i+1] or sticker[1][i+2] 이고
현재 뗀 위치의 행이 1인 경우엔
sticker[0][i+1] or sticker[0][i+2] 가 된다.
다시 말하면 sticker[1][i] 위치의 최대 값을 결정하는 것은
Math.max(sticker[0][i-1], sticker[0][i-2]) + score[1][i] 이고
sticker[0][i] 위치의 최대 값을 결정하는 것은
Math.max(sticker[1][i-1], sticker[1][i-2]) + score[0][i] 인 것이다.
이후 0행과 1행의 마지막 위치인 n의 값을 서로 대소 비교를 해줌으로써 점수의 최대 값을 구할 수 있다.
결과가 하나가 아니고 테스트케이스 별로 나오기 때문에 StringBuilder 에 담아서 한번에 출력하도록 했다.
🚨CODE
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());
StringBuilder sb = new StringBuilder();
for(int tc = 0; tc<T; tc++) {
int n = Integer.parseInt(br.readLine());
int[][] score = new int[2][n+1];
int[][] dp = new int[2][n+1];
StringTokenizer st = new StringTokenizer(br.readLine());
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i = 1; i<=n; i++) {
score[0][i] = Integer.parseInt(st.nextToken());
score[1][i] = Integer.parseInt(st2.nextToken());
}
dp[0][1] = score[0][1];
dp[1][1] = score[1][1];
for(int i = 2; i<=n; i++) {
dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + score[0][i];
dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + score[1][i];
}
sb.append(Math.max(dp[0][n], dp[1][n])).append("\n");
}
System.out.println(sb);
}
}
728x90
반응형
'코딩테스트' 카테고리의 다른 글
[JAVA] 백준 11048 - 이동하기 (0) | 2024.03.19 |
---|---|
[JAVA] 백준 1238 - 파티 (0) | 2024.03.18 |
[JAVA] 백준 1932 - 정수 삼각형 (0) | 2024.03.10 |
[JAVA] 백준 2156 - 포도주 시식 (0) | 2024.03.06 |
[JAVA] 백준 1699 - 제곱수의 합 (0) | 2024.03.04 |