백준 2461. 대표 선수

tose33 2022. 7. 23. 15:12

2461번: 대표 선수

입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한

www.acmicpc.net

투포인터 문제.

쉽지 않은 문제였다, 처음에 방향을 잘못잡아 엄청 오래걸렸다.

모든 능력치를 {능력치, 소속 반} 의 형태로 저장하고, 능력치를 기준으로 오름차순 정렬한다.

그 후 left = 0, right =0 부터 시작해서 right 포인터를 이동시키고, 현재 까지 포함된 각 반별 학생수를 저장해 나간다.

모든 반이 최소 1명씩 포함됐다면 ans를 최솟값으로 갱신하고, left 포인터를 오른쪽으로 이동시킬수 있는 만큼 이동시킨다.

(모든 반이 최소 1명씩 포함되는한 계속 오른쪽으로)