[BOJ][9465] 스티커

1. 문제 링크

https://www.acmicpc.net/problem/9465

2. 사용 알고리즘

DP

3. 풀이

d[n][a] : 2 * n 스티커를 뜯었을 때 점수의 최대값, n열의 상태는 a

• 상태 a [0] : 위X, 아래X, [1] : 위X, 아래O, [2] : 위O, 아래X

• d[n][0] = max(d[n - 1][0], d[n - 1][1], d[n - 1][2])

• d[n][1] = max(d[n - 1][0], d[n - 1][2]) + p[n][1]

• d[n][2] = max(d[n - 1][0], d[n - 1][1]) + p[n][0]

∴ max(d[n][0] + d[n][1] + d[n][2])

4. 소스 코드

4-1. C++

4-1-1. Top-Down

https://github.com/dev-aiden/problem-solving/blob/main/boj/9465.cpp

#include <iostream>
#include <algorithm>

using namespace std;

int d[100003][3];
int arr[100003][2];

int solve(int n, int a) {
    if (n == 0) return 0;
    if (d[n][a] != -1) return d[n][a];
    if (a == 0) d[n][a] = max(max(solve(n - 1, 0), solve(n - 1, 1)), solve(n - 1, 2));
    else if (a == 1) d[n][a] = max(solve(n - 1, 0), solve(n - 1, 2)) + arr[n][1];
    else if (a == 2) d[n][a] = max(solve(n - 1, 0), solve(n - 1, 1)) + arr[n][0];
    return d[n][a];
}

int main(void) {
    ios_base::sync_with_stdio(false);
    int t; for (cin >> t; t--;) {
        for (int i = 0; i <= 100000; ++i) {
            for (int j = 0; j < 3; ++j) d[i][j] = -1;
        }
        int n; cin >> n;
        for (int i = 0; i < 2; ++i) {
            for (int j = 1; j <= n; ++j) cin >> arr[j][i];
        }
        cout << max(max(solve(n, 0), solve(n, 1)), solve(n, 2)) << "\n";
    }
    return 0;
}

4-1-2. Bottom-Up

https://github.com/dev-aiden/problem-solving/blob/main/boj/9465_2.cpp

#include <iostream>
#include <algorithm>

using namespace std;

int d[100003][3];
int arr[100003][2];

int main(void) {
    ios_base::sync_with_stdio(false);
    int t; for (cin >> t; t--;) {
        int n; cin >> n;
        for (int i = 0; i < 2; ++i) {
            for (int j = 1; j <= n; ++j) cin >> arr[j][i];
        }
        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][1];
            d[i][2] = max(d[i - 1][0], d[i - 1][1]) + arr[i][0];
        }
        cout << max(max(d[n][0], d[n][1]), d[n][2]) << "\n";
    }
    return 0;
}

4-2. JAVA

4-2-1. Top-Down

https://github.com/dev-aiden/problem-solving/blob/main/boj/9465.java

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

import static java.lang.Math.max;

public class Main {

    static int d[][] = new int[100003][3];
    static int arr[][] = new int[100003][2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        for(int t = Integer.parseInt(br.readLine()); t-- > 0;) {
            for (int i = 0; i <= 100000; ++i) {
                for (int j = 0; j < 3; ++j) d[i][j] = -1;
            }
            int n = Integer.parseInt(br.readLine());
            for(int i = 0; i < 2; ++i) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j = 1; j <= n; ++j) arr[j][i] = Integer.parseInt(st.nextToken());
            }
            sb.append(max(max(solve(n, 0), solve(n, 1)), solve(n, 2))).append("\n");
        }
        System.out.println(sb);
    }

    public static int solve(int n, int a) {
        if (n == 0) return 0;
        if (d[n][a] != -1) return d[n][a];
        if (a == 0) d[n][a] = max(max(solve(n - 1, 0), solve(n - 1, 1)), solve(n - 1, 2));
        else if (a == 1) d[n][a] = max(solve(n - 1, 0), solve(n - 1, 2)) + arr[n][1];
        else if (a == 2) d[n][a] = max(solve(n - 1, 0), solve(n - 1, 1)) + arr[n][0];
        return d[n][a];
    }
}

4-2-2. Bottom-Up

https://github.com/dev-aiden/problem-solving/blob/main/boj/9465_2.java

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

import static java.lang.Math.max;

public class Main {

    static int d[][] = new int[100003][3];
    static int arr[][] = new int[100003][2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        for(int t = Integer.parseInt(br.readLine()); t-- > 0;) {
            int n = Integer.parseInt(br.readLine());
            for(int i = 0; i < 2; ++i) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j = 1; j <= n; ++j) arr[j][i] = Integer.parseInt(st.nextToken());
            }
            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][1];
                d[i][2] = max(d[i - 1][0], d[i - 1][1]) + arr[i][0];
            }
            sb.append(max(max(d[n][0], d[n][1]), d[n][2])).append("\n");
        }
        System.out.println(sb);
    }
}