[BAEKJOON] 9465 스티커

문제 요약

• 알고리즘 분류: 동적계획법, dp
• 난이도: Silver1
• 문제내용:
  • 스티커가 2 × n개가 있다. 하지만 하나 자르면 상하좌우 사용을 못한다.
  • 사용할수 있는 스티커중 가중치 최대값을 구해라.

• 사이트: https://www.acmicpc.net/problem/9465

9465번: 스티커

문제풀이

 이번 문제는 테스트 개수 T를 주고 길이가 최대 100,000이다. 브루드포스 같은 알고리즘으로 풀면 시간초과가 나서 가장 좋은 방법은 동적계획법으로 해결하는 방법이다. 동적계획법의 자세한 설명은 여기에 확인 해보면 된다.

문제 접근 방법

 동적계획법은 구현 능력보다 아이디어나 접근 하는 방법을 많이 요구해서 아이디어만 잘 생

 문제 예제1번을 표로 나타낸것이고 전체적인 스티커에서 선택한것중 답은 노란색으로 칠했다.

 일단 경우의 수가 여러가지가 있는데 한개씩 확인 해보자

N = 1인 경우

1인 경우에는 50과 10중 하나만 선택하면 된다. 그래서 답은 50이다.

N = 2 인 경우

2인 경우에는 노란색 칠한것과 초록색 칠한 영역을 보면 된다. 2일때 자를수 있는 경우의 수는 2가지이다. 노란색 칠한 영역과 초록색 칠한 영역더해서 최대값을 구하면 된다. 그러면 답은 100이라는것을 알수있다.

N 이 3이상일 경우

  여기서 부터 중요하다.  이제 부터 점화식을 세우는 과정을 볼것이다.

(0, i)이전에 나올수 있는 경우의 수가 노란책 칠한 영역과 주황색 칠한 영역이다. 노란색영역은(1, i -1), (0, i - 2) ....  합한 결과이고 주황색 영역은 (1, i - 2)까지 나오는 영역이다.  결론으로는 (0, i) 기준에서는 (1, i - 1)까지 최대값과 (0, i - 2)최대 값중 큰 것이랑 더한면 된다.

 (1, i) 이전에 나올 수 있는 경우 보면 (0, i - 1), (0, i - 2)중 가장 큰 값을 더하면된다.

그래서 점화식은 아래와 같은 식이 나올수가 있다.

 연산이 끝났으면 가장 큰값을 출력하면된다. 여기서 궁금한점이 있을건인데 맨끝에 값을 출력하면 되지 않나고 물어보는데 다시 앞에 그림을 보면 i인덱스 이전에 올 수 있는 가능성이 (x, i - 1), (x, i - 2)이다.  연산후에도 똑같이 맨 끝과 그 앞에 값이 더 클 가능성도 있어서 dp 연산후 가장 큰값을 구하는 이유가 된다.

예제

 앞에 이론 만으로 이해하기 힘들거 같아서 예제1로 어떻게 dp 연산이 되는지 보여 주겠다.

 i = 0

 0번째 인덱스는 n = 1일때랑 비슷하다 스티커 0번째 인덱스 그대로 넣어 주면된다.

i = 1

1번째 인덱스는 n = 2를 보면 가능성이 2가지가 있다고 했다. 그대로 대각선 끼리 더해서 넣어 주면 된다.

i = 2

 2번째 인덱스는 (0, 2)일때와 (1, 2)를 나누어서 설명하면된다. (0, 2)는 주황색 영역중 큰 값이랑 더하면되고, (1, 2)는 빨간색 영역중 큰 값을 더하면된다.

i = 3

 3번째 인덱스도 2번째 인덱스 처럼 (0, 3)는 주황색 영역중 큰 값이랑 더하면되고, (1, 3)는 빨간색 영역중 큰 값을 더하면된다.

i = 4

 4번째 인덱스도 앞에처럼 연산 해주면 되고 dp 배열중 가장 큰 값을 구하면 된다. 그래서 예제의 답은 260나온다.

Code

Python

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    sticker = [list(map(int, input().split())) for _ in range(2)]
    dp = [[0] * n  for _ in range(2)]
    dp[0][0] = sticker[0][0]
    dp[1][0] = sticker[1][0]
    if n > 1:
        dp[0][1] = sticker[1][0] + sticker[0][1]
        dp[1][1] = sticker[0][0] + sticker[1][1]
    if n > 2:
        for i in range(2, n):
            dp[0][i] = sticker[0][i] + max(dp[1][i - 1], dp[1][i -2])
            dp[1][i] = sticker[1][i] + max(dp[0][i - 1], dp[0][i -2])
    print(max(map(max, dp)))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int n;
		int[][] sticker, dp;
		while(T-- > 0) {
			n = Integer.parseInt(br.readLine());
			sticker = new int[2][n];
			dp = new int[2][n];
			for(int i = 0; i < 2; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0; j < n; j++) {
					sticker[i][j] = Integer.parseInt(st.nextToken()); 
				}				
			}
			dp[0][0] = sticker[0][0];
			dp[1][0] = sticker[1][0];
			if(n > 1) {
				dp[0][1] = sticker[0][1] + dp[1][0];
				dp[1][1] = sticker[1][1] + dp[0][0];
			}
			if(n > 2) {
				for(int i = 2; i < n; i++) {
					dp[0][i] = sticker[0][i] + Math.max(dp[1][i - 1], dp[1][i - 2]);
					dp[1][i] = sticker[1][i] + Math.max(dp[0][i - 1], dp[0][i - 2]);
				}
			}
			System.out.println(Math.max(Arrays.stream(dp[0]).max().getAsInt(),Arrays.stream(dp[1]).max().getAsInt()));
		}
			
	}
	
}