[백준] 2229번. 조 짜기(JAVA)

문제

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

---

풀이(50분)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N + 1];
        int[] scores = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            scores[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= N; i++) {
            int max = scores[i];
            int min = scores[i];
            for (int j = i; j >= 1; j--) {
                max = Math.max(max, scores[j]);
                min = Math.min(min, scores[j]);
                dp[i] = Math.max(dp[i], max - min + dp[j - 1]);
            }
        }

        System.out.println(dp[N]);
    }

}

---

문제 풀이 전략

 

문제를 처음 접했을 때 나이차이가 많이 나면 좋지 않다!라는 것은 읽었지만, 그에 대한 적절한 조건이 없어 정렬 후 양쪽에서 줄여오는 느낌으로 구현했다.

하지만, 풀이를 계속 해도 결론에 다다르지 못했고, 다른 분들의 코드를 참고한 결과 dp 코드라는 것을 알게 되었다.

 

풀이는 다음과 같다. 자기 자신까지의 그룹에서 하나씩 빼가며 모두 비교하는 것이다.

즉 dp[5]라고 치면

5 혼자 + 4까지의 그룹 값(이때 그룹 값이라 함은 dp의 값)

5와 4의 그룹 값 + 3까지의 그룹값

5, 4, 3의 그룹 값 + 2까지의 그룹 값

이런 식으로 모두 구하는 것이다.

문제를 정확히 이해하지 못해 긴 시간을 소모한 것 같다.