백준 2229번 - 조 짜기

조 짜기 문제 바로 가기

풀이 날짜: 2026-03-12

baekjoon 알고리즘 문제 풀이

풀이 코드


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

dp = [0] * n

for i in range(n):
    max_v = score[i]
    min_v = score[i]

    for j in range(i,n):
        max_v = max(max_v, score[j])
        min_v = min(min_v, score[j])

        if i == 0:
            prev = 0
        else:
            prev = dp[i-1]

        dp[j] = max(dp[j], prev + (max_v - min_v))

print(dp[n-1])

접근 방법

이 문제는 학생들의 점수가 주어졌을 때, 학생들을 연속된 여러 그룹으로 나누어 각 그룹의 점수 차이(max − min)의 합을 최대화하는 문제이다. 중요한 조건은 학생들의 순서를 바꿀 수 없고, 반드시 연속된 구간으로만 그룹을 만들 수 있다는 점이다. 처음에는 모든 경우의 수로 그룹을 나누는 브루트포스를 떠올릴 수 있지만, 가능한 경우가 매우 많기 때문에 비효율적이다. 따라서 이미 계산한 결과를 활용하는 동적 계획법(DP)을 이용해 문제를 해결할 수 있었다.

DP 정의

dp[i] = 0번째 학생부터 i번째 학생까지 고려했을 때 만들 수 있는 최대 점수

즉, dp[i]는 i번째 학생까지 그룹을 최적으로 나누었을 때 얻을 수 있는 최대 점수를 의미한다. 최종적으로 구해야 하는 값은 모든 학생을 고려한 dp[n-1]이다.

핵심 아이디어

[0 ~ i-1] | [i ~ j]

이 문제의 핵심은 마지막 그룹을 어디서 시작할 것인지 결정하는 것이다. 만약 j번째 학생에서 마지막 그룹이 끝난다면, 그 그룹의 시작 위치는 어떤 i일 수 있다.
이때 전체 점수는 다음과 같이 계산할 수 있다.
앞부분의 최대 점수 + 마지막 그룹 점수 = dp[i-1] + (max(i~j) - min(i~j)) 따라서 가능한 모든 i에 대해 위 값을 계산하고, 그 중 최댓값을 dp[j]에 저장하면 된다.

구현 방식

그룹의 시작 위치 i를 먼저 정하고, 끝 위치 j를 오른쪽으로 확장하는 방식으로 구현했다.

즉, i~j 구간을 하나의 그룹으로 보고 점수를 계산한다. j를 증가시키면서 그룹이 확장되므로 매번 해당 구간의 최대값과 최소값을 갱신하여 (max - min) 값을 계산했다.

코드에서 중요했던 부분

prev = dp[i-1] if i > 0 else 0

prev는 현재 그룹 앞부분(0~i-1)의 최대 점수이다.
dp[j] = max(dp[j], prev + (max_v - min_v))

(max_v - min_v)는 현재 그룹(i~j)의 점수이다.

문제를 통해 배운 점

이 문제는 DP와 구간 확장 기법을 함께 사용하는 대표적인 문제이다. 핵심은 특정 위치에서 끝나는 그룹을 생각하는 것이 아니라, 마지막 그룹의 시작 위치를 바꾸면서 전체 최적값을 갱신하는 것이다. 또한 구간의 최대값과 최소값을 반복 계산하지 않고 확장하면서 갱신하는 방식이 시간 복잡도를 줄이는 중요한 포인트였다.

Vienna sausage