[백준 31501] DP(small) - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/31501

 

문제

이 문제는 DP (Large)와 문제의 수 제한, 질문의 수 제한, 문제의 난이도 제한이 다른 문제이다.

DP는 DYNAMIC Porani의 약자이다.

DYNAMIC한 포라니는 가능한 문제를 DYNAMIC하게 푸는 것을 좋아한다. DYNAMIC한 문제 풀이란 문제의 번호와 난이도가 모두 증가하도록 가능한 한 많이 푸는 것이다.

방학을 맞은 포라니는 알고리즘 능력 향상을 위해 선배로부터 추천 문제 셋을 받았다. 나태한 포라니는 모든 문제를 풀고 싶지 않다. 만약 선배로부터 어떤 문제를 풀라는 지시를 받았을 때, 그 문제를 포함하여 DYNAMIC하게 문제를 풀었을 경우 몇 문제를 풀어야 하는지 알려주자.

 

입력

첫 번째 줄에 문제의 수 N(1 ≤ N ≤ 3000)과 쿼리의 수 Q(1 ≤ Q ≤ N)가 공백으로 구분되어 주어진다.

두 번째 줄에 문제의 난이도를 나타내는 음이 아닌 정수 Di(1 ≤ i ≤ N;0 ≤ Di ≤ 3000)가 문제 번호의 순서대로 공백으로 구분되어 주어진다. 문제 번호는 1부터 시작하는 연속된 양의 정수이다.

세 번째 줄부터 Q 개의 줄에 걸쳐 선배가 풀라고 한 문제의 번호 Ai (1 ≤ i ≤ Q;1 ≤ Ai ≤ N)가 주어진다. 쿼리로 주어지는 문제의 번호는 중복되지 않는다.

 

출력

Q 개의 줄에 걸쳐, i번째 줄에 i번째 선배의 지시에 따라 풀어야 하는 문제 수를 순서대로 출력한다.

풀이

접근법

1. 해당 지점이 꼭 포함이 되어야하니까 해당 지점 기준 이전 + 이후를 하면 될 것 같다.
2. 그러려면 dp 배열을 2개를 생성해서 누적해서 사용하면 되겠다.
3. 만약 쿼리가 들어오면 해당 지점 기분 이전 + 이후 - 1(겹치는 부분) 을 하면 될 것 같다.

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int Q=Integer.parseInt(st.nextToken());
        int[] arr = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++) arr[i] = Integer.parseInt(st.nextToken());
        // 1. 해당 지점이 꼭 포함이 되어야하니까 해당 지점 기준 이전 + 이후를 하면 될 것 같다.
        // 2. 그러려면 dp 배열을 2개를 생성해서 누적해서 사용하면 되겠다.
        int[] prefix = new int[N+1];
        int[] suffix = new int[N+1];
        // 이전 ~ 해당 지점
        for(int i=1;i<=N;i++) {
            for(int j=0;j<i;j++) {
                if (arr[i] > arr[j]) prefix[i] = Math.max(prefix[i], prefix[j]);
            }
            prefix[i]++;
        }
        // 해당 지점 ~ 이후
        for(int i=N;i>=1;i--) {
            for(int j=i+1;j<=N;j++) {
                if (arr[i] < arr[j]) suffix[i] = Math.max(suffix[i], suffix[j]);
            }
            suffix[i]++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<Q;i++) {
            int q = Integer.parseInt(br.readLine());
            // 3. 만약 쿼리가 들어오면 해당 지점 기분 이전 + 이후 - 1(겹치는 부분) 을 하면 될 것 같다.
            sb.append(prefix[q] + suffix[q] - 1).append("\n");
        }
        System.out.println(sb);
    }
}

 

중간에 놀아서.. 한 15분쯤 걸렸다 !