[BOJ] 2229 조짜기 (Python3)

문제

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

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

정답 코드

n = int(input())
students = list(map(int, input().split()))


dp = [0 for i in range(n + 1)]

for i in range(1, n + 1):
    for j in reversed(range(i)):
        temp = students[j : i]
        
        maxValue = max(temp)
        minValue = min(temp)
        
        dp[i] = max(dp[i], dp[j] + maxValue - minValue)
        
print(dp[n])     

20

문제 해설

나이를 기준으로 나열된 숫자를 부분집합으로 나누어 그 부분집합의 최댓값 - 최솟값을 구하고, 모든 각각의 부분집합의 최댓값 - 최솟값의 합이 최대가 되도록 하는 문제이다.

딱봐도 모든 부분집합의 수를 구하려면 n의 최댓값이 1000 이므로 시간초과가 나고, 부분집합을 어떻게 묶느냐가 최종 값을 결정하므로 다이나믹 프로그래밍 문제이다.

그냥 딱봐도 브루트 포스로 안될 것 같은데? dfs나 bfs도 아님 -> DP 라고 생각하면 마음이 편하다…

DP 문제를 풀때는 우선 브루트 포스로 어떻게 풀지를 고민해보고, 이를 메모리에 어떤식으로 저장해야하는지를 생각하여 이전에 구한 값을 저장하여 한번 구한 값을 기준으로 새로 구한 값을 갱신하는 식으로 풀이를 생각해보는것이 좋다.

먼저 n + 1개의 배열인 dp를 만들어준다.

우리는 모든 각 부분집합의 최댓값 - 최솟값을 더한 값을 구해야하는데, 계속 이렇게 부를 수는 없으므로 설명하기 편하게 이 값을 학습조직력이라고 해보자.

위 문제의 경우, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]의 배열이 생성된다.

각 인덱스는 0부터 인덱스까지의 그룹의 최대 학습 조직력을 나타낸다.

예를들어 인덱스가 3이라면 1번째부터 3번째 학생까지의 가장 이상적인 학습조직력의 값이다.

그럼 이제 for문을 돌며 학생을 하나씩 추가해가며 가장 이상적인 학습조직력을 구해보면,

2 5 7 1 3 4 5 6 9 3

1번째 학생까지의 최대 학습 조직력

현재 그룹 = [2]

1) 2가 혼자 그룹인 경우

학습 조직력 = 2 - 2 = 0

따라서 dp[1] = 0

2번째 학생까지의 최대 학습 조직력

현재 그룹 = [2, 5]

1) 5가 혼자 그룹인 경우

d[1] = [2] 그룹

학습 조직력 = d[1] + 5 - 5 = 0

2) [5, 2]가 그룹인 경우

학습 조직력 = 5 - 2 = 3

따라서 dp[2] = 3

3번째 학생까지의 최대 학습 조직력

현재 그룹 = [2, 5, 7]

1) 7이 혼자 그룹일 경우

d[2] = [2, 5] 그룹

학습 조직력 = d[2] + 7 - 7 = 3

2) [5, 7]이 그룹인 경우

d[1] = [2] 그룹

d[1] + 7 - 5 = 2

3) [2, 5, 7]이 그룹인 경우

학습 조직력 = 7 - 2 = 5

따라서 dp[3] = 5

이런식으로 그룹을 나눠가며 이전 값을 사용하여 값을 구하면 된다.