[백준] 2229 조짜기

문제 링크

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

사용 알고리즘

• DP

풀이

문제를 풀어서 설명하면 연속된 학생들끼리 묶어서 조를 구성할 경우, 각 조들의 잘 짜여진 정도의 합의 최댓값을 구하는 문제이다.

 

따라서, 각 학생별로 해당 학생까지 각 조들의 잘 짜여진 정도의 합의 최댓값을 저장하는 dp 배열이 필요하다.

▶︎ `dp[i] = dp[i]까지 각 조들의 잘 짜여진 정도의 합의 최댓값`

 

그리고 i번 학생까지 조가 잘 짜여진 정도의 합을 알기 위해선,

기존에 구했던 0 ~ i번 학생(j라고 가정)에서의 조가 잘 짜여진 정도의 합에

`max(i번 학생의 점수, j번 학생의 점수) - min(i번 학생의 점수, j번 학생의 점수)`를 더했을 때 최대가 되는 값을 구하면 된다.

코드

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

n, students = int(input()), [int(x) for x in input().split()]

dp = [0] * (n + 1)
for i in range(1, n + 1):
    for j in range(i, 0, -1):
        minimal = min(students[i - 1], students[j - 1])
        maximum = max(students[i - 1], students[j - 1])
        dp[i] = max(
            dp[i],
            dp[j - 1] + maximum - minimal
        )
print(dp[-1])