(Python/🥇5)백준알고리즘 2229번 : 조 짜기

 

문제 바로가기 

조 짜기

 

문제:

알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 학생들을 같은 조로 묶어서 서로 자극을 받으며 공부하도록 만들기 위함이다. 따라서 가급적이면 실력 차이가 많이 나도록 조를 편성하는 것이 유리하다. 하지만 조를 편성할 때 같은 조에 속하게 된 학생들의 나이 차이가 많이 날 경우에는 오히려 부정적인 효과가 나타날 수도 있다. 따라서 선생님들은 우선 학생들을 나이 순서대로 정렬한 다음에, 적당히 학생들을 나누는 방식으로 조를 짜기로 하였다. 조의 개수는 상관이 없다. 각각의 조가 잘 짜여진 정도는 그 조에 속해있는 가장 점수가 높은 학생의 점수와 가장 점수가 낮은 학생의 점수의 차이가 된다. 또한 전체적으로 조가 잘 짜여진 정도는, 각각의 조가 잘 짜여진 정도의 합으로 나타난다. 한 명으로 조가 구성되는 경우에는 그 조의 잘 짜여진 정도가 0이 된다(가장 높은 점수와 가장 낮은 점수가 같으므로). 학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하는 프로그램을 작성하시오.

입력:

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

 

출력:

첫째 줄에 답을 출력한다.

 

풀이:

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=221535723529 

[백준] 2229 - 조 짜기

너무 헷갈리고 해서 이 분의 코드를 참고했다.

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())  # 학생의 수 

lst = list(map(int, sys.stdin.readline().split(" ")))  # 학생들의 점수

if n <= 1:  # 학생의 수가 1 이하라면 두 명 이하로 조를 편성할 수 없음
    print(0)
    exit(0)

dp = [0] * (n+1)  # dp 리스트 

for i in range(1, n+1):  # 각 학생들을 순서대로 추가
    max_v, min_v = 0, 10001  # 현재까지 선택한 학생들의 가장 높은 점수와 가장 낮은 점수 초기화

    for j in range(i, 0, -1):  # 현재까지 선택한 학생들 중에서 가장 나이가 어린 학생부터 순서대로 확인
        max_v = max(max_v, lst[j-1])  # 가장 높은 점수를 max_v에 저장
        min_v = min(min_v, lst[j-1])  # 가장 낮은 점수를 min_v에 저장
        dp[i] = max(dp[i], max_v - min_v + dp[j - 1])  
        # dp[i]는 현재까지 선택한 학생들로 이루어진 조에서 가장 점수가 높은 학생과 가장 점수가 낮은 학생의 차이와,
        #이전 조까지의 잘 짜여진 정도를 더한 값으로 갱신

print(dp[n])  # 최댓값

 

dp 에는 각 명수 마다 최댓값을 최신화 시킨다.

 

이 문제는 연속수열에서 최댓값이다, 왜냐하면

문제에서  하지만 조를 편성할 때 같은 조에 속하게 된 학생들의 나이 차이가 많이 날 경우에는 오히려 부정적인 효과가 나타날 수도 있다. 따라서 선생님들은 우선 학생들을 나이 순서대로 정렬한 다음에 >> 이 부분 때문이다.

 

즉 연속된 수열이야 한다는것이다.

 

그러면 새로운 나뉘어진 수열에 새로운 값을 추가하면서 비교를 해주면 된다.

바로 예시 들어간다.

 

2 5 7 1 3 4 8 6 9 3

일때 n= 4까지 해보겠다.

 

 

•  n =1
  • 최대(2) 최소(2) = 0 dp[0] = 0
• n = 2
  • 2 / 5 = dp[1]
  • 25 = 5-2 =3
  • 즉 dp[2] = 3
•  n = 3
  • 2/5/7 = 0
  • 25/7 = dp[2] + 0 = 3
  • 2/57 = dp[1] + 7-5 = 2
  • 257 = 5
  • 즉 dp[3] = 5
• n = 4
  • 2/5/7/1 = 0
  • 257/1 = dp[3] = 5 
  • 25/71 = dp[2] + 7-1 = 9
  • 2/571 = dp[1] + 7-1 = 6
  • 2571 = 7-1 = 6
  • 즉 dp[4] = 9 

이런식이다. 이해가 됐으면 좋겠다.

 

이 것을 코드로 나타내면 된다.

 

for i in range(1, n+1):  # 각 학생들을 순서대로 추가하며 최적의 조합을 찾음
    max_v, min_v = 0, 10001  # 현재까지 선택한 학생들의 가장 높은 점수와 가장 낮은 점수 초기화

    for j in range(i, 0, -1):  # 현재까지 선택한 학생들 중에서 가장 나이가 어린 학생부터 순서대로 확인
        max_v = max(max_v, lst[j-1])  # 현재까지 선택한 학생들 중 가장 높은 점수를 max_v에 저장
        min_v = min(min_v, lst[j-1])  # 현재까지 선택한 학생들 중 가장 낮은 점수를 min_v에 저장
        dp[i] = max(dp[i], max_v - min_v + dp[j - 1])  # dp[i]는 현재까지 선택한 학생들로 이루어진 조에서 가장 점수가 높은 학생과 가장 점수가 낮은 학생의 차이와, 이전 조까지의 잘 짜여진 정도를 더한 값으로 갱신

당연히 이 부분이 이해가 안 될거라고 생각된다.

 

바로 예시 들어간다 i가 4라고 생각하면 .2571 일때 비교를 하면된다.

i 가 4이면  j는 4부터 역순으로 돌아간다.

 

그럼 처음에는 dp[4] , 0-0 + dp[3] 이렇게 되는것이다. 즉 조로 안 들어가고 혼자 남게되는것이다. 그리고 나서 j가 1개 내려가고

 max_v와 , min_v 는 1로 바뀌어져 있다.

 

그 다음 포문은 25/ 71 이렇게 한 조가 된다는 것인데.

j 가 3이 되면서 min_v 는 1로 유지가 되지만 max_v 가 7로 바뀐다.

그럼 뒷 수열 71 에서 잘짜여진정도는 6점이고 앞에는 dp[3-1] + 6 이고, j가 4일때 dp[3] 에 5가 들어있으니

그 두개를 비교하여 들어가면된다.

 

그냥 간단하게 말하면

1234

123  / 4

12  / 34

1 / 234

이렇게 다 비교한다고 보면된다.

 

다이나믹프로그래밍에서 한계를 느낀다.