알고리즘/동적 계획법(Dynamic Programming)

2229-백준-조 짜기

easysheep 2023. 3. 24. 21:40

1. 문제 출처

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

 

2229번: 조 짜기

알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는

www.acmicpc.net

2. 풀이

다이나믹 프로그래밍 이용하면 된다.

# 입력
n = int(input())

students = list(map(int,input().split()))
g = [0 for _ in range(1+n)]
# 다이나믹 프로그래밍을 이용하여

for i in range(n+1):
    ma = 0
    mi = 10001
    for j in range(i,0,-1):
        ma = max(ma,students[j-1])
        mi = min(mi,students[j-1])
        g[i] = max(g[i], ma - mi + g[j - 1])
print(g[n])