백준 2229. 조 짜기

티스토리 뷰

tose33 2023. 2. 13. 15:07

2229번: 조 짜기

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

www.acmicpc.net

d[i] : 1번 ~ i번 학생까지 조를 짰을때 조가 잘 짜여진 정도의 최댓값.

점화식:

d[i] = max(d[i], d[j-1] + (maxVal - minVal))

예를들어 d[4] 를 구한다고 해보자

d[4] 는 1번 ~ 4번 학생까지 조를 짰을때 조가 잘 짜여진 정도의 최댓값이다.

1~3번 학생까지 조를 짰을때 조가 잘 짜여진 정도의 최댓값 d[3] + (4번~4번 학생들중 점수의 최댓값 - 최솟값).

1~2번 학생까지 조를 짰을때 조가 잘 짜여진 정도의 최댓값 d[2] + (3번~4번 학생들중 점수의 최댓값 - 최솟값).

1~1번 학생까지 조를 짰을때 조가 잘 짜여진 정도의 최댓값 d[2] + (2번~4번 학생들중 점수의 최댓값 - 최솟값).

이 중 최댓값이 d[4] 의 값이 된다.

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함