[백준] [DP] 2229. 조 짜기

2229. 조 짜기 

2229번: 조 짜기

 

• 풀이
  • 이 문제의 설명이 조금 부족했는데, 나이순서로 정렬한 다음에 조를 짠다는 의미
    • -> i~j 나이 까지의 사람들이 한 조가 되는것
    • 줄이 붙어있는 사람들끼리는 한 조가되어야지 군데군데 한명씩 뽑아서 조를 이룰 수는 없다는 의미
  • n번째 학생 조를 짤때 n+1개 만큼의 연산이 필요하다
    • n혼자 조인경우
    • n-1과 함께 조인경우
    • n-2....1,0번과 함께 조인경우
      • -> n*(n+1) => O(n^2) 
      • n이 1000이니까 가능
  • 코드
    • j==i-1 일때는 max_val=min_val  
      • dp[i] 값에는 dp[i-1] 그 전까지의 합이 처음 들어가게 되어있음
    • 설명 이해는 아래 링크

[출처] [백준] 2229 - 조 짜기|작성자 occidere

여기까지 보였다시피 k 번째 점수를 입력받았으면

k번째 점수 혼자 그룹 + k - 1 번째 까지 적당히 그룹핑 했을 때의 최대값

k - 1 번째 점수 그룹 + k - 2 번째 까지 적당히 그룹핑 했을 때의 최대값

.....

k - (n-1) 번째 점수 그룹 + 1번째 점수 혼자 그룹핑 했을 때의 최대값

 

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

# 나이순 모여있는애들끼리 한 조
for i in range(1, n+1):
    max_val = 0
    min_val = int(1e9)
    for j in range(i-1, -1, -1):
        max_val = max(max_val, score[j])
        min_val = min(min_val, score[j])
        dp[i] = max(dp[i], max_val-min_val+dp[j])

print(dp[n])