내가 개발해볼게!!
[BOJ] 9465번: 스티커 본문
https://www.acmicpc.net/problem/9465
문제
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.
난이도
실버 1
Sol
DP(점화식) - 각 열의 두 번째 스티커부터 대각선 방향의 한 칸 앞, 두 칸 앞의 스티커 중 점수가 높은 스티커를 선택해 더해나간다. dp 배열 각 열의 마지막 행은 해당 스티커를 선택했을 때 얻을 수 있는 점수의 최댓값이 된다. 두 행 중 최댓값을 찾아 출력.
public class B9465_스티커 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
for(int i=0; i<T; i++){
int n = Integer.parseInt(bf.readLine());
int[][] stickers = new int[2][n+1]; // 노드의 이전 노드와 그 이전 노드를 고려하기 위해 n+1으로 크기 설정
int[][] dp = new int[2][n+1];
for(int j=0; j<2; j++){
String[] input = bf.readLine().split(" ");
// StringTokenizer -> String.split()으로 고치면서 시간은 줄고 메모리는 늘었다
for(int k=1; k<n+1; k++) stickers[j][k] = Integer.parseInt(input[k-1]);
}
// input
dp[0][1] = stickers[0][1];
dp[1][1] = stickers[1][1];
// 초기값 설정
for(int j=2; j<n+1; j++){
dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + stickers[0][j];
dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + stickers[1][j];
} // 대각선 방향의 한 칸 앞, 두 칸 앞의 스티커 고려
// operation
System.out.println(Math.max(dp[0][n], dp[1][n]));
// 각 열의 마지막 스티커까지 확인한 후 최댓값을 출력
// output
}
}
}
🙄
- 입력단에서 StringTokenizer를 String.split()으로 수정하면서 실행 시간은 줄어들고 필요 메모리는 증가했다
- stickers, dp 배열의 크기(n+1) 주의!
다이나믹 프로그래밍 문제는 왠지 풀 때마다 새로운 느낌이고, 점화식 세우는 게 어렵다.. 많이 풀어서 얼른 DP에 익숙해졌으면 좋겠다
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 1012번: 유기농 배추 (0) | 2023.08.15 |
---|---|
[BOJ] 1932번: 정수 삼각형(Java) (0) | 2023.08.10 |
[BOJ] 1495번: 기타리스트(java) (0) | 2023.08.04 |
[BOJ] 1149번: RGB거리 (0) | 2023.08.02 |
[BOJ] 1446번: 지름길 (0) | 2023.07.28 |