[Python/파이썬] 백준 2229번 조 짜기

2229번: 조 짜기

 

문제

알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 학생들을 같은 조로 묶어서 서로 자극을 받으며 공부하도록 만들기 위함이다. 따라서 가급적이면 실력 차이가 많이 나도록 조를 편성하는 것이 유리하다.

하지만 조를 편성할 때 같은 조에 속하게 된 학생들의 나이 차이가 많이 날 경우에는 오히려 부정적인 효과가 나타날 수도 있다. 따라서 선생님들은 우선 학생들을 나이 순서대로 정렬한 다음에, 적당히 학생들을 나누는 방식으로 조를 짜기로 하였다. 조의 개수는 상관이 없다.

각각의 조가 잘 짜여진 정도는 그 조에 속해있는 가장 점수가 높은 학생의 점수와 가장 점수가 낮은 학생의 점수의 차이가 된다. 또한 전체적으로 조가 잘 짜여진 정도는, 각각의 조가 잘 짜여진 정도의 합으로 나타난다. 한 명으로 조가 구성되는 경우에는 그 조의 잘 짜여진 정도가 0이 된다(가장 높은 점수와 가장 낮은 점수가 같으므로).

학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. 다음 줄에는 N명의 학생들의 점수가 나이 순서대로 주어진다. 각 학생의 점수는 0 이상 10,000 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

코드

n = int(input())
score = list(map(int, input().split()))

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

print(dp[n])

 

dp 배열에는 i(1 ≤ i ≤ n)번째 학생까지의 조가 잘 짜여진 정도의 최대값이 저장된다.

i번째 학생을 하나씩 추가할 때마다 맨 끝의 조 인원을 1명에서 i명으로 증가시키며 dp[i]에 최대값을 넣는다.

 

시간복잡도가 O($N^2$)로 효율성이 떨어진다고 생각하여 다른 사람들의 풀이를 찾아보니 맨 끝의 조 인원을 하나씩 늘려가며 탐색할 때 최대값, 최소값이 갱신되지 않는다면 더이상 탐색하지 않도록 하여 시간효율성을 크게 끌어올릴 수 있는 코드가 있었다.

n = int(input())
score = list(map(int, input().split()))

dp = [0] * (n+1)
for i in range(n):
    dp[i+1] = dp[i]
    max_v = min_v = score[i]
    j = i-1
    while j >= 0 and (score[j] < min_v or score[j] > max_v):
        max_v = max(score[j], max_v)
        min_v = min(score[j], min_v)
        dp[i+1] = max(dp[i+1], dp[j]+(max_v-min_v))
        j -= 1

print(dp[n])