자바 백준 9465번
실버 1
https://www.acmicpc.net/problem/9465
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
문제 보기

분류: 다이나믹 프로그래밍
코드 보기
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 테스트 케이스 개수 입력 int T = sc.nextInt(); for (int t = 0; t < T; t++) { // 스티커 열 개수 입력 int n = sc.nextInt(); // 스티커의 점수를 저장할 배열 int[][] sticker = new int[2][n]; // 스티커 점수 입력 for (int i = 0; i < 2; i++) { for (int j = 0; j < n; j++) { sticker[i][j] = sc.nextInt(); } } // 스티커의 최대 점수를 계산하는 함수 사용 int result = getMaxStickerScore(n, sticker); // 결과 출력 System.out.println(result); } } // 스티커의 최대 점수를 계산하는 함수 private static int getMaxStickerScore(int n, int[][] sticker) { // 동적 프로그래밍을 위한 배열 int[][] dp = new int[2][n]; // 초기값 설정: 첫 번째 열의 스티커 점수로 초기화 dp[0][0] = sticker[0][0]; // 첫 번째 열의 위쪽 행 스티커 선택 dp[1][0] = sticker[1][0]; // 첫 번째 열의 아래쪽 행 스티커 선택 // dp 배열 채우기 for (int i = 1; i < n; i++) { // 현재 열의 위쪽 행 스티커를 선택했을 때의 최대 점수 // i가 0 또는 1일 때는 i - 1 또는 i - 2가 음수로 나가게 되므로 이런 경우에 대한 예외 처리 dp[0][i] = Math.max(dp[1][i - 1], i >= 2 ? dp[1][i - 2] : 0) + sticker[0][i]; // 현재 열의 아래쪽 행 스티커를 선택했을 때의 최대 점수 // i가 0 또는 1일 때는 i - 1 또는 i - 2가 음수로 나가게 되므로 이런 경우에 대한 예외 처리 dp[1][i] = Math.max(dp[0][i - 1], i >= 2 ? dp[0][i - 2] : 0) + sticker[1][i]; } // 마지막 열에서 최대값 구하기 return Math.max(dp[0][n - 1], dp[1][n - 1]); } }
'공부하기 > 백준' 카테고리의 다른 글
[Java] 백준 풀기 20920 - 영단어 암기는 괴로워 (0) | 2023.09.26 |
---|---|
[Java] 백준 풀기 9933 - 민균이의 비밀번호 (0) | 2023.09.25 |
[Java] 백준 풀기 2556 - 별 찍기 14 (0) | 2023.09.23 |
[Java] 백준 풀기 10990 - 별 찍기 15 (0) | 2023.09.23 |
[Java] 백준 풀기 17219 - 비밀번호 찾기 (0) | 2023.09.21 |