[BOJ] #2229 조 짜기

조 짜기

백준 #2229

---

📌 문제

예제 입력

10
2 5 7 1 3 4 8 6 9 3

예제 출력

20

---

📌 풀이

Logic

• 학생 수 N, 학생들의 점수 scores 입력 받기
• DP 테이블 생성
  • i번째 학생까지 고려할 때, 마지막 조의 시작점을 K로 정의
  • K를 i - 1 ~ 0까지 줄여가며 diff 계산
    • 각 학생을 마지막으로 포함하는 조의 모든 경우 시도
  • 기존의 dp[i]값과 dp[k] + diff 중 큰 값으로 갱신

# 변수명
N : 학생 수
scores : 학생들의 점수 리스트
diff : 해당 범위에서 max - min 값

Python

import sys

N = int(sys.stdin.readline().strip())
scores = list(map(int, sys.stdin.readline().split()))

dp = [0 for _ in range(N + 1)]

for i in range(N + 1):
    for k in range(i - 1, -1, -1):
        if (k == i):
            continue

        diff = max(scores[k:i]) - min(scores[k:i])
        dp[i] = max (dp[k] + diff, dp[i])

print(dp[-1])

---

✏️ 새로운 내용

-

---

📚 회고

💡 DP

• dp[i] = max(dp[i], dp[k]+ diff)
• 문제를 이해하는 데 어려움을 겪어, 해당 점화식을 생각하는 데 오래 걸렸다.
  
• i번째까지의 최적해(dp[i])는 k번째에서 끊는다.
• (k ~ i - 1까지 한 조로 묶었을 때의 점수) + (k-1까지의 최적해)
• 이 중에서 최댓값을 선택하는 방식이다.