[백준] 2491번 : 수열 – JAVA [자바]

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

2491번: 수열

 

---

• 문제

 

---

• 문제 풀이

백준 2491번 수열은 DP를 이용해서 푸는 문제이다. DP 이론을 더 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

 

이 문제에서는 연속하는 수열 중에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 수열의 길이를 출력하는 프로그램만 만들면 된다.

 

예제들을 한 번 보겠다.

 

예제 1)

1 2 2 4 4 5 7 7 2

1  2  2  4  4  5  7  7  2

하이라이트 된 부분들이 같거나 증가하므로 가장 긴 수열의 길이는 8이다.

 

예제 2)

4 1 3 3 2 2 9 2 3

4  1  3  3  2  2  9  2  3

하이라이트 된 부분이 같거나 감소하므로 가장 긴 수열의 길이는 4이다.

 

예제 3)

1 5 3 6 4 7 1 3 2 9 5

1  5  3  6  4  7  1  3  2  9  5

이 예제에서는 여러 개가 있지만 같거나 증가하는, 또는 감소하는 가장 긴 수열의 길이는 2이다.

 

---

• 코드

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[3][n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        dp[0][1] = Integer.parseInt(st.nextToken());
        dp[1][1] = 1;
        dp[2][1] = 1;
        int max = 1;
        for (int i = 2; i <= n; i++) {
            dp[0][i] = Integer.parseInt(st.nextToken());
            if (dp[0][i] >= dp[0][i-1]) {
                dp[1][i] = dp[1][i-1]+1;
            } else {
                dp[1][i] = 1;
            }
            if (dp[0][i] <= dp[0][i-1]) {
                dp[2][i] = dp[2][i-1]+1;
            } else {
                dp[2][i] = 1;
            }
            max = Math.max(max, Math.max(dp[1][i], dp[2][i]));
        }
        System.out.print(max);
    }
}

 

---

• 후기

간단한 실버 4 난이도의 DP 문제였던 거 같다.