BOJ 30960 조별 과제
https://www.acmicpc.net/problem/30960 30960번: 조별 과제 학번이 $3, 1$인 사람을 한 조로 묶고, $4, 5, 9$인 사람을 한 조로 묶으면 각 조의 어색함은 $(3-1) = 2$와 $(9-4) = 5$이고, 합은 $7$이다. 이 방법이 각 조의 어색함의 합을 최소로 하는 방법이다. www.acmicpc.net 정해는 정렬+누적합이지만, 아이디어가 떠오르지 않아 DP로 해결했습니다. 본 글에선 두 가지 방법 모두 소개합니다. 1. 정렬+누적합 일단 입력받은 배열을 정렬한 상태라고 합시다. 앞에서부터 3명씩 묶을 사람을 정합니다. 맨 처음 3명을 묶을 경우 어색함의 총합은 $(a_{2}-a_{0}) + (a_{4}-a_{3}) + (a_{6}-a_{5})$입니다. 이..
알고리즘 문제풀이
2024. 1. 31. 20:39