[DP] 백준 2229번 조짜기 - JAVA

 

 

 

구현문제처럼 풀었다가 맥도 못추린 문제...

 

싸피 때 양교수님께선 항상 말씀하셨지...

"코드가 복잡하다는 느낌이 들면 아 내가 잘못하고 있구나"

항상 생각할 것...

 

2번의 불발된 시도 끝에 답안을 찾아보았다.

내가 가장 도움을 느낀 블로그는 이거다!

 

https://yoggaebi.tistory.com/46

[백준, DP, JAVA] P.2299 조짜기

 

 

글 자체는 이해가 되지 않았는데, 코드를 보며 한땀한땀 하다보니 이해가 팍 갔다!

 

 

 

---

1. 출처

---

 

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

2229번: 조 짜기

 

• 나이순대로 학생들의 점수가 주어진다.
• 최대한 나이차이가 나지 않게 팀을 구성해라! 즉 연속된 학생들을 팀으로 짜야한다는 의미
• 팀의 할당되는 인원 수는 재각각이다. 제한이 없다. (4명, 2명, 100명 이렇게 짜도 된다는 의미)
• 팀의 잘짜여진 정도는 가장 높은 점수 - 가장 낮은 점수이다. 높을수록 좋다. 
• 팀이 모두 짜여졌을 때 총 점수가 높게해라.

 

 

---

2. 설계

---

 

구현 그리디 문제인가 했는데, DP 문제였다. 입력값으로 학생의 점수를 1개씩 받으면서 현재 학생들로 이룰 수 있는 최대 잘짜여진 정도를 dp테이블에 저장하면 된다. 예제로 주어진 수를 가지고 dp테이블의 현황을 나타내면 아래와 같다.

 

예제 입력

10
2 5 7 1 3 4 8 6 9 3

 

예제 출력

20

 

 

1) N = 10이 들어옴

dp와 score 테이블을 N+1크기로 만들어라. 왜냐하면 학생번호를 1번부터 매겨줄 예정이기 때문이다. 또한 1번 학생의 최대값을 계산할 때 0번 인덱스를 접근할 것이기 때문에 out of bound를 내지 않기 위함이기도 하다. 때문에 dp[0] = 0이다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String numbers = br.readLine();
StringTokenizer st = new StringTokenizer(numbers," ");

int[] score = new int[N+1];
int[] dp = new int[N+1];

dp[0] = 0;

 

 

2) 그럼 score과 dp에는 어떻게 값이 들어가는가?

2 5 7 1 3 4 8 6 9 3

 

위 숫자가 하나씩 들어온다고 가정한다.

 

 

2-1) 2가 들어왔다.

j는 i-1부터 1까지만 도는데 현재 i-1은 0이므로 반복문을 돌지 않고, max값을 넣어준다.

 

 

2-2) 5가 들어왔다.

i=2, j=1이면 최대값 5 - 최소값 2 = 3이다. 그리고, 이전까지 잘짜여진 최대의 값은 dp[j-1] = dp[0] = 0이다.

3+0 = 3이고, max = 0보다 크기 때문에 3으로 갱신된다. 즉, dp[2] = max(3)이 된다.

 

 

 

 

2-3) 7이 들어왔다.

i=3, j=2이면 최대값 7- 최소값 5 = 2이다. 그리고, 이전까지 잘짜여진 최대의 값은 dp[j-1] = dp[1] = 0이다.

현재 과정에서 나온 2+0 = 2라는 값은 max = 3보다 작기 때문에 max는 갱신되지 않는다.

 

 

다음 과정으로 i=3, j=1이면 최대값 7 - 최소값 2 = 5이다. 그리고, 이전까지 잘짜여진 최대의 값은 dp[j-1] = dp[0] = 0이다.

5+0 = 5이고, max = 3보다 크기 때문에 5로 갱신된다. 즉, dp[3] = max(5)가 된다.

 

 

2-4) 1이 들어왔다.

i=4, j=3이면 최대값 7 - 최소값 1 = 6이다. 그리고, 이전까지 잘짜여진 최대의 값은 dp[j-1] = dp[2] =3이다.

6+3 = 9이고, max = 5보다 크기 때문에 9로 갱신된다.

 

나는 여기서 dp테이블의 과정에 대해 감이 왔다.

i=4, i=3이라는 것은 i가 최대값 j가 최소값 (혹은 최대 최소가 바뀌거나)이라고 가정했을 때 잘짜여진 값과

그 이전의 잘짜여진 값 (1번학생 + 2번학생의 팀) dp[2]의 값을 합쳤을 때

전체 잘짜여진 값을 높일 수 있니?를 묻고 있는 것이다.

 

 

즉, dp 테이블은 n번 학생까지 들어왔을 때 잘짜여진 값의 최대는 몇인가? 를 나타낸다.

 

 

2-5) 전체 양상

 

 

---

3. 전체 코드

---

 

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

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

        int[] score = new int[N+1];
        int[] dp = new int[N+1];
        dp[0] = 0;
        int max = 0;
        for(int i=1;i<=N;i++){
            score[i] = Integer.parseInt(st.nextToken());
            for(int j=i-1;j>=1;j--){
                max = Math.max(max, Math.abs(score[i]-score[j])+dp[j-1]);
            }
            dp[i] = max;
        }

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