(9) [C++, Java] 백준 No.9465 : 스티커

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-10-DP-문제-풀이9-백준-No9465-스티커

 

# C++(Bottom-up방식)

- max함수 쓸 때 STL은 인자 2개만 받는 것으로 정의되어있으니 2개씩 나눠서 해줘야 한다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001][2];   // N번째라는 용어를 사용하여 알고리즘을 생각했으므로 index를 [1~100000][0~1] 를 사용할 수 있도록 함
int d[100001][3];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    for (int test_case = 0; test_case < T; test_case++)
    {
        int n;
        cin >> n;

        for(int i = 1; i <= n; i++)
            cin >> arr[i][0];

        for(int i = 1; i <= n; i++)
            cin >> arr[i][1];

        d[0][0] = d[0][1] = d[0][2] = 0;

        for (int i = 1; i <= n; i++)
        {
            d[i][0] = max(max(d[i-1][0], d[i-1][1]), d[i-1][2]);
            d[i][1] = max(d[i-1][0], d[i-1][2]) + arr[i][0];
            d[i][2] = max(d[i-1][0], d[i-1][1]) + arr[i][1];
        }
        
        cout << max(max(d[n][0], d[n][1]), d[n][2]) << "\n";
    }
}

# Java

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.valueOf(br.readLine());
        while (t-- > 0) {
            int n = Integer.valueOf(br.readLine());
            long[][] a = new long[n+1][2];
            {
                String[] line = br.readLine().split(" ");
                for (int i=1; i<=n; i++) {
                    a[i][0] = Long.valueOf(line[i-1]);
                }
            }
            {
                String[] line = br.readLine().split(" ");
                for (int i=1; i<=n; i++) {
                    a[i][1] = Long.valueOf(line[i-1]);
                }
            }
            long[][] d = new long[n+1][3];
            for (int i=1; i<=n; i++) {
                d[i][0] = Math.max(d[i-1][0],Math.max(d[i-1][1],d[i-1][2]));
                d[i][1] = Math.max(d[i-1][0],d[i-1][2])+a[i][0];
                d[i][2] = Math.max(d[i-1][0],d[i-1][1])+a[i][1];
            }
            long ans = 0;
            ans = Math.max(d[n][0], Math.max(d[n][1], d[n][2]));
            System.out.println(ans);
        }
    }
}