[백준] Silver II. 가장 큰 증가하는 부분 수열

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

 

 

사용 알고리즘

• 다이나믹 프로그래밍 

 

풀이

 

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

/*
    테이블: d[i]: i번째 원소를 방문할 때 증가하는 부분 수열의 최댓값
    점화식: d[i] = max(d[i], d[j] + s[i])
 */
public class Main {
    static int n;
    static int [] s, d;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        d = new int[n];
        s = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            s[i] = Integer.parseInt(st.nextToken());
            d[i] = s[i];
        }

        int max = d[0];
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if (s[i] > s[j]) {
                    d[i] = Math.max(d[i], s[i] + d[j]);
                }
            }
            max = Math.max(max, d[i]);
        }

        System.out.println(max);
    }
}

 

회고

 

테이블

d[i]: i번째 원소를 방문할 때 증가하는 부분 수열의 최댓값 

 

점화식

d[i] = max(d[i], d[j] + s[i])

 

 

문제에서 예제로 수열이 이렇게 주어질 때,

1 100 2 50 60 3 5 6 7 8

 

 

s[i]

1

100

2

50

60

3

5

6

7

8

 

d[i]

1

100

3

53

113

6

11

17

24

32

 

이런식으로 d[] 배열은 증가수열의 합이 저장 되어야 한다.

 

문제를 풀면서 헷갈렸던 부분은 나는 

d[i] = d[i-1] + s[i]

 

이런식으로 d[i-1]까지의 증가수열의 합과 s[i]를 더해주었는데, 이렇게 어렵게 생각하지말자..! 

 

그리고 문제에서 또 실수했던 것은 d 원소들을 처음에 할당해줘야 한다.

for(int i = 0; i < n; i++) {
    s[i] = Integer.parseInt(st.nextToken());
    d[i] = s[i];
}

 

점화식을 세우는 아이디어는 점점 가까워지고 있으니 숙달되도록 연습하자