백준 31721번: 수강신청 (Python)

문제링크

https://www.acmicpc.net/problem/31721

문제 총평

- 아이디어의 중요성

 

문제 접근방식

 

- 이 문제의 경우 그리디를 이용해 이 문제만의 풀이법을 짜야하는 애드 혹 문제입니다.

- 먼저 n개의 수강과목들을 받으면서 a >= b 인경우 무조건 정답에 +1을 해줍니다.

- 그 이유는 a > b인 경우 달구가 반드시 수강신청이 가능하고 a == b인 경우 달구가 수강신청을 해야만 수강 정원이 가득 차므로 풀이에 신경쓰지 않고 정답에 +1을 해주면 됩니다.

- 그 이외에는 a 만 리스트에 넣어줍니다, 그 이유는 b는 사실상 의미없는 값이므로 a만 저장해 둡니다.

- 그 후 역정렬을 해주고 그 이유는 이후에 설명드리겟습니다.

- 이제 리스트가 빌때까지 반복문을 돌립니다.

1. 먼저 달구가 리스트에서 하나를 pop 하고 정답에 +1을 해줍니다.

2. 전교생에서 달구가 빠진 m-1 이 0이 될때까지 과목을 한개씩 제거해 줍니다.

3. 이때 남은 학생으로도 한 과목을 제거할 수 없다면 (수강 정원 > 남은 학생) 그 다음의 과목의 수강 정원을 남은 학생만큼 빼주고 다시 리스트에 넣고 그 전에 뽑은 값도 다시 넣어줍니다.

4. 이때 그 다음 수강과목의 정원에 빼주는 이유는 어처피 마지막의 요소는 다음 반복문에서 달구가 신청을 하기때문에 최악이 아니고 그 다음 수강과목의 정원을 빼주는게 최악이 되기 때문입니다. (가장중요한 부분)

- 이렇게 구한 ans를 출력합니다.

 

정답코드 

import sys; input = sys.stdin.readline
n,m = map(int,input().split())
ans = 0
arr = []
for _ in range(n):
    a,b = map(int,input().split())
    if a >= b: ans += 1
    else:
        arr.append(a)
arr.sort(reverse=True)
while arr:
    ans += 1
    arr.pop()
    tem = m-1
    while arr and tem > 0:
        a = arr.pop()
        if tem < a:
            if not arr:
                ans += 1
                print(ans)
                exit()
            c = arr.pop()
            arr.append(c-tem)
            arr.append(a)
            break
        tem -= a
print(ans)

 

문제 풀이 후 생각

- 사실 아이디어가 전부인 문제라서 풀이의 4번만 잘 생각하신다면 누구나 풀 수 있을거 같습니다.

 

 

모르는게 있다면 댓글 또는 godzz733@naver.com으로 메일 남겨 주세요