[백준] 9465 - 스티커 (JAVA)

1. 소요시간 : 15분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 1
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/9465
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 사고과정

n이 100,000 까지니 O(n) 이나 O(nlogn) 으로 풀어야 했다. 그렇다면 바로 다이나믹 프로그래밍으로 풀어야 한다.
처음에 상,하,좌,우는 방문이 안된다는 문구를 보고는 바로 그래프 이론이 떠올랐다..
하지만 그렇게 하면 문제도 복잡해지고 시간복잡도도 초과할 것이니
O(n)의 시간복잡도를 가지는 dp를 이용해야겠다고 생각했다.

3. 풀이과정

dp로 계속 최댓값을 기록해야한다.
예제 입력을 보면서 점화식을 유도해보려고 했다.
우선 기본적으로는
dp[i][0] = dp[i-1][1] + arr[i][0]
dp[i][1] = dp[i-1][0] + arr[i][1] 이다.
하지만 예제만 봐도 알 수 있듯이 내 전 스티커를 건너 뛸 수도 있다.
그렇기에 거기에 한 가지 조건이 더 붙는다.
dp[i][0] = dp[i-2][1] + arr[i][0]
dp[i][1] = dp[i-2][0] + arr[i][0]
이 될 수도 있는 것이다.
둘을 혼용하면 결국
dp[i][0] = Math.max(dp[i-1][1] , dp[i-2][1] ) +arr[i][0] 이 된다.

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;


		int t=Integer.parseInt(br.readLine());
		
		while(t-->0) {
			int n=Integer.parseInt(br.readLine());
			int arr[][]=new int[n+1][2];
			String line1[]=br.readLine().split(" ");
			String line2[]=br.readLine().split(" ");
			for(int i=1;i<arr.length;i++) {
				arr[i][0]=Integer.parseInt(line1[i-1]);
				arr[i][1]=Integer.parseInt(line2[i-1]);
			}
			int dp[][]=new int[n+1][2];
			dp[1][0]=arr[1][0];
			dp[1][1]=arr[1][1];
			for(int i=2;i<dp.length;i++) {
				dp[i][0]=Math.max(dp[i-1][1],dp[i-2][1])+arr[i][0];
				dp[i][1]=Math.max(dp[i-1][0],dp[i-2][0])+arr[i][1];
			}
			System.out.println(Math.max(dp[n][0],dp[n][1]));

		}

	}
}

5. 결과

6. 회고

dp도 하면 늘긴 느는구나 ㅠㅠ
이 문제는 사실 한 3주 쯤 전에 클래스 4 문제로 흘깃 봤었는데
당시에는 어떻게 풀지 막막해서 다음에 풀어야지 하고 보류해 뒀었다.
그런데 오늘 하루종일 dp만 하니까 결국 이 문제도 풀 수 있었다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212