[고등부] 2024 KOI 1차대회 대비 모의고사 (1주차)

편의상 1부터 N까지 번호가 붙은 정올시의 도둑들은 모두 한 번 도둑질을 할 때 정확히 일정량의 보석만을 훔쳐가는 정직한 도둑들이다.

i번 도둑의 경우 A_i개의 보석을 훔쳐가는데, 만약 도둑질을 하려는 집이 너무 가난하여 A_i개 미만의 보석을 갖고 있는 경우 훔치지 않는다.

또한 정올시의 도둑들은 모두 서열이 확실하여 1번 도둑부터 시작하여 N번 도둑까지 차례로 도둑질을 시도하고, N번 도둑의 차례가 끝나면 다시 1번 도둑이 들어가 도둑질을 한다.

정올시 최고 부자집 정올이의 집엔 K개의 보석이 있다. 도둑들이 도둑질을 모두 끝내고 나면 총 몇 개의 보석이 남아있을지 알아보자.