[boj] 백준 2209 조짜기 python 풀이

새로운 사람이 추가되면 생길 수 있는 새로운 팀을 모든 경우의 수를 따져가며 dp에 max(총점수)를 기록

 

예를 들어,

 

10
2 5 7 1 3 4 8 6 9 3

 

위 테스트 케이스의 경우에는

2, 5 다음 7이 새로 들어왔을 때, 생길 수 있는 새로운 팀은

2, 5 // 7 

2 // 5, 7

2,5,7 (한 팀)

.

.

이런식

 

그런데 이전 dp에 빨간 글씨 경우는 모두 저장되어 있으므로

새롭게 생길 수 있는 팀의 점수에 가져다 더하면 됨.

모든 경우의 수를 보면서 제일 큰 점수를 가지는 경우를 dp에 저장.

 

 

문제)

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

2229번: 조 짜기

 

코드)

import sys
input = sys.stdin.readline

N = int(input().strip())
student_list = list(map(int, input().split()))
dp = [0 for _ in range(N+1)]

for i in range(N+1):
    for k in range(i-1, -1, -1): 
        new_team_score = max(student_list[k:i]) - min(student_list[k:i]) # 새로운 사람이 포함되어 구성될 수 있는 팀의 점수
        dp[i] = max(dp[k] + new_team_score, dp[i])
        
print(dp[-1])