[BOJ] 9465 스티커

스티커

풀이

• 그놈의 디피... 용기를 내서 도전해보았다.
• 반복문을 사용하는 bottom-up 방식을 이용.
• dp[0][i] or dp[1][i] : 이 칸 까지의 최대 값 저장하는 공간.
  처음엔 dp 1차원 배열로도 가능한가? 생각했지만 현재 내가 0행 칸을 보고 있는지 1행 칸을 보고 있는지에 따라 메모이제이션 방식이 달라지기 때문에 2차원 배열로 구현했다.
• 만약 0행 칸을 보고 있는 경우, 대각선 왼쪽 아래 칸+ 현재 칸 을 선택한 경우와 내 바로 왼쪽 칸을 선택하고 현재 칸은 선택하지 않은 경우 중 큰 값을 비교하여 메모해주면 된다.

🙆‍♀️ 정답 코드

import java.util.*;
import java.io.*;
public class BOJ9465 {
    public static void main(String[] args) throws Exception{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++){
            int n = Integer.parseInt(br.readLine());
            int[][] map = new int[2][n+1];
            int[][] dp = new int[2][n+1];
            StringTokenizer st;
            for(int j=0;j<2;j++){
                st = new StringTokenizer(br.readLine());
                for(int m=0;m<n;m++){
                    map[j][m] = Integer.parseInt(st.nextToken());
                }
            }
            dp[0][0] = map[0][0];
            dp[1][0] = map[1][0];
            for(int k=1;k<n;k++){
                dp[0][k] = Math.max(dp[1][k-1]+map[0][k],dp[0][k-1]);
                dp[1][k] = Math.max(dp[0][k-1]+map[1][k],dp[1][k-1]);
            }
            System.out.println(Math.max(dp[0][n-1],dp[1][n-1]));
        }
    }
}