[백준] 9465번 스티커

[CMSSKKK]

TITLE

스티커

LINK

• 문제 출처 사이트 : 백준
• Link

📷 Screenshots

댓글 양식

• 아래 양식을 복사한 뒤 [shift]+[tab] 2회를 하고 작성하여 주세요

    ### 풀이 언어

    - python/java

    ### 코드

    ```python/java

    ```

    ### 핵심 로직 혹은 자료구조

    - 

    ### 시간 복잡도

    - O(  )

[CMSSKKK]

풀이 언어

• java

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        StringBuilder sb = new StringBuilder();
        while(t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[][] scores = new int[2][n];
            for (int i = 0; i < 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    scores[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            sb.append(findMax(scores, n)).append('\n');
        }

        System.out.println(sb.toString());

    }

    private static int findMax(int[][] scores, int n) {
        if(n != 1) {
            scores[0][1] += scores[1][0];
            scores[1][1] += scores[0][0];

            for (int i = 2; i < n; i++) {
                int max = Math.max(scores[0][i - 2], scores[1][i - 2]);
                scores[0][i] += Math.max(scores[1][i-1], max);
                scores[1][i] += Math.max(scores[0][i-1], max);
            }
        }
        
        return Math.max(scores[0][n-1], scores[1][n-1]);

    }
}

핵심 로직 혹은 자료구조

• dp

시간 복잡도

• O( )

[Seokho-Ham]

풀이 언어

• java

코드

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            int caseLength = Integer.parseInt(br.readLine());
            int[][] arr = createArray(br, caseLength);
            int[][] dp = new int[2][caseLength];

            if (caseLength == 1) {
                System.out.println(Math.max(arr[0][0], arr[1][0]));
                continue;
            }
            
            dp[0][0] = arr[0][0];
            dp[1][0] = arr[1][0];
            dp[0][1] = arr[1][0] + arr[0][1];
            dp[1][1] = arr[0][0] + arr[1][1];



            for (int j = 2; j < caseLength; j++) {
                dp[0][j] = Math.max(Math.max(dp[0][j - 2] + arr[0][j], dp[1][j - 2] + arr[0][j]), dp[1][j - 1] + arr[0][j]);
                dp[1][j] = Math.max(Math.max(dp[0][j - 2] + arr[1][j], dp[1][j - 2] + arr[1][j]), dp[0][j - 1] + arr[1][j]);
            }
            System.out.println(Math.max(dp[0][caseLength-1],dp[1][caseLength-1]));
        }


    }

    private static int[][] createArray(BufferedReader br, int caseLength) throws IOException {
        int[][] arr = new int[2][caseLength];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < caseLength; i++) {
            arr[0][i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < caseLength; i++) {
            arr[1][i] = Integer.parseInt(st.nextToken());
        }
        return arr;
    }
}

핵심 로직 혹은 자료구조

시간 복잡도

• O( )