[백준/2229] 조 짜기 (Python)

Problem :

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:08:14

 

---

 

문제 설명

 

 

알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 학생들을 같은 조로 묶어서 서로 자극을 받으며 공부하도록 만들기 위함이다. 따라서 가급적이면 실력 차이가 많이 나도록 조를 편성하는 것이 유리하다.

하지만 조를 편성할 때 같은 조에 속하게 된 학생들의 나이 차이가 많이 날 경우에는 오히려 부정적인 효과가 나타날 수도 있다. 따라서 선생님들은 우선 학생들을 나이 순서대로 정렬한 다음에, 적당히 학생들을 나누는 방식으로 조를 짜기로 하였다. 조의 개수는 상관이 없다.

각각의 조가 잘 짜여진 정도는 그 조에 속해있는 가장 점수가 높은 학생의 점수와 가장 점수가 낮은 학생의 점수의 차이가 된다. 또한 전체적으로 조가 잘 짜여진 정도는, 각각의 조가 잘 짜여진 정도의 합으로 나타난다. 한 명으로 조가 구성되는 경우에는 그 조의 잘 짜여진 정도가 0이 된다(가장 높은 점수와 가장 낮은 점수가 같으므로).

학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 N이 주어진다. 다음 줄에는 N명의 학생들의 점수가 나이 순서대로 주어진다. 각 학생의 점수는 0 이상 10,000 이하의 정수이다.

 

출력

 

첫째 줄에 답을 출력한다.

 

입력 예시

 

10
2 5 7 1 3 4 8 6 9 3

 

출력 예시

 

20

 

 

---

 

풀이

 

DP로 풀이해보도록 하자. i번째 사람까지 조를 짰을 때 최대 점수합을 DP[i]라고 가정하자.

 

그렇다면, i번째 사람부터 j번째 사람까지의 조를 한 번에 짠다면, 그 조의 점수는 max(score[i, j]) - min(score[i, j])가 되고, 이 때의 j번째 사람까지의 점수 최대합 DP[j]는 이 점수 및 i-1번째 조까지의 부분 최대합 값으로 업데이트될 것이다. 즉

 

DP[j] = max(DP[j], max(score[i, j]) - min(score[i, j]) + DP[i-1])

 

의 형태가 된다. i == 0일 때는 이 값이 0이 됨에 주의하자.

 

풀이 코드

N = int(input())

score_list = list(map(int, input().split()))
dp = [0]*N
for i in range(N) :
  minval = maxval = score_list[i]
  for j in range(i+1, N) :
    minval = min(minval, score_list[j])
    maxval = max(maxval, score_list[j])
    dpval = dp[i-1] if i > 0 else 0
    dp[j] = max(dp[j], maxval - minval + dpval)

print(dp[-1])

풀이 완료!