백준 20120 호반우와 리듬게임

문제

호반우들 사이에서는 저번달 새로 출시한 리듬게임인 호스가 유행이다. 호스는 연속된 노트를 처리할 수록 보너스 점수를 받게 되는데 그 과정은 이러하다.

노트에는 점수가 정수로 매겨져있다. 하지만 호스는 다른 리듬게임과 다르게 점수가 음수일 수도 있다.
호반우가 연속으로 처리한 노트의 개수를 콤보라고 하자. 노트 하나를 칠 때마다 (누적 콤보)×(현재 노트) 값이 총 점수에 추가된다.
연속으로 3개의 노트를 놓치면 지금까지 얻은 점수가 0점이 되고 더 이상 점수를 얻을 수 없다.
호반우는 모든 노트를 주어진 순서대로 처리해야 한다.
호반우는 모든 노트를 처리해서 풀 콤보를 받았지만 최대 점수를 받을 수 없었다. 호반우를 위해 호반우가 얻을 수 있는 최대 점수를 계산해주는 프로그램을 만들어주자!

부분집합과 DP의 콜라보 N이 1000이기 때문에 그냥 부분집합은 시간초과다
그러나 DP로 중간값을 메모해놓고 visited 배열을 이용하여 실제 그 구간에 방문한 적이 있다면 메모값을 return 시키는 식으로 방문 최적화를 하면 한번 방문한 곳에는 다시 방문할 필요가 없어진다
메모를 할 때는 무엇을 메모할 것인가가 중요한데
현재 위치 + 콤보 수 + 실패 수 ( 이 세가지가 구간의 정보이고 메모를 해야할 대상이다)

python

def func(idx, combo, fail):
    if visited[idx][combo][fail]:
        return DP[idx][combo][fail]
    visited[idx][combo][fail] = True


    if idx == N:
        return 0

    DP[idx][combo][fail] = func(idx + 1, combo + 1, 0) + combo * arr[idx]
    if fail < 2:
        DP[idx][combo][fail] = max(DP[idx][combo][fail], func(idx+1, 1, fail + 1))

    return DP[idx][combo][fail]



if __name__ == "__main__":

    N = int(input())
    arr = list(map(int, input().split()))
    DP = [[[0] * 3 for _ in range(N + 2)]for _ in range(N + 1)]
    visited = [[[False] * 3 for _ in range(N+2)]for _ in range(N + 1)]

    rst = func(0, 1, 0)
    print(0) if rst < 0 else print(rst)

java

import java.util.*;
import java.io.*;
public class Main {
    static boolean visit[][][];
    static long  DP[][][];
    static int N;
    static long p[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        p = new long[N + 1];
        for(int i = 1; i <= N; i++) {
            p[i] = Long.parseLong(st.nextToken());
        }

        visit = new boolean[1002][1002][3];
        // record DP[현재 위치][콤보 수][놓친 것]
        DP = new long[1002][1002][3];
        long res = func(1, 1, 0);
        if(N >= 3) res = Math.max(res ,0L);


        System.out.println(res);
    }

    public static long func(int cur, int combo, int fail) {
        if(visit[cur][combo][fail]) return DP[cur][combo][fail];
        visit[cur][combo][fail] = true;
        if(cur == N + 1) {
            DP[cur][combo][fail] = 0;
            return DP[cur][combo][fail];
        }
        DP[cur][combo][fail] = func(cur + 1, combo + 1, 0) + p[cur] * combo;

        if(fail < 2) DP[cur][combo][fail] = Math.max(DP[cur][combo][fail] , func(cur + 1, 1, fail + 1));

        return DP[cur][combo][fail];
    }
}