[BOJ][Python3/PyPy3] 13904 - 과제

다른 사람의 코드를 보고 아이디어를 얻었음에도 구현을 정확하게 하지 못해

결국 질문게시판의 반례 코드를 보고 해결한 문제.

'과제'를 풀면서 깨달은 것을 정리해보고자 한다.

 

과제의 문제 설명 자체는 간단하다.

마감일, 과제 완료시 얻는 점수에 대한 정보가 과제 수만큼 주어진다.

이제 남은 기간동안 효율적으로 최대한의 점수를 얻기만 하면 된다.

 

나는 당연히 첫날부터 과제를 어떻게 선택하는 것이 좋은지에 대해 고민했다.

점수가 가장 높은 순으로 고르는 것이 제일 먼저 떠올랐다.

그리고 반례도 바로 떠올랐다 ㅋㅋ

3 30

2 20

1 10

최대값은 60이지만, 점수가 높은 순으로 뽑았다가는 50밖에 얻지 못한다.

 

그렇다면 마감일이 빠른 순으로 뽑으면 되는가?

과제 문제의 예시 입력을 보면 하루 남은 과제는 아예 뽑지조차 않는다.

그렇다면 마감일이 빠른 순도 아니다.

 

여기에서 멘붕이 왔다.

마감일이 빠른순, 점수가 높은 순이라는 직관적인 정렬 기준말고 다른 요소가 있는가?

그것을 고민하고 고민하는데 집중했다.

아무리 고민해도 답이 안나와서 결국 다른 사람의 아이디어를 검색했다.

 

다른 사람의 코드를 통해 알게된 아이디어는 간단했다.

첫날부터 세는게 아니라, 마감일부터 세는것이다.

마감일부터 세서, 그 날 할 수 있는 과제들 중 가장 점수가 높은 과제를 해결하는 것이다.

회의실 배정이 '회의가 끝나는 시간' 순으로 정렬하는 것이 최적해인 것과 비슷해보였다.

거꾸로 생각하기!

 

예시를 들면 이해가 빠르다.

7

4 60

4 40

1 20

2 50

3 30

4 10

6 5

 

예시입력이다.

먼저 마감일이 많이 남은 순 -> 점수가 높은 순으로 정렬한다.

6 5

4 60

4 40

4 10

3 30

2 50

1 20

 

그 다음 6일째인 날부터 1일째인 날까지 반복을 돈다.

 

6일째 할 수 있는 과제 => '6 5' => 점수를 많이 주는걸 한다.

5일째 할 수 있는 과제 => '없음' => 할 수 있는 과제가 없으니 건너뛴다.

4일째 할 수 있는 과제 => '4 60', '4 40', '4 10' => 점수를 많이주는 걸 한다.

3일째 할 수 있는 과제 => '4 40', '4 10', '3 30' => 점수를 많이 주는 걸 한다.

2일째 할 수 있는 과제 => '4 10', '3 30', '2 50' => 점수를 많이 주는 걸 한다.

1일째 할 수 있는 과제 => '4 10', '3 30', 1 20' => 점수를 많이 주는 걸 한다.

 

이제 이 알고리즘을 코드로 구현해보았다. (아래는 틀린코드이다.)

# 13904 과제
import sys
n = int(input())
homeworks = []
for _ in range(n):
    deadline, score = map(int, sys.stdin.readline().split())
    homeworks.append((deadline, score))
homeworks.sort()
can    = []
date   = homeworks[-1][0]
answer = 0
while True:
    if date == 0 or not homeworks:
        break
    while homeworks[-1][0] >= date:
        can.append(homeworks.pop()[1])
        if not homeworks:
            break
    date -= 1
    if not can:
        continue
    can.sort()
    answer += can.pop()
print(answer)

(마감일, 점수) 튜플로 묶어서 리스트에 저장한다음

그냥 기본 정렬을 시켰다. 그러면 마감일이 증가하는 순으로 정렬되고

마감일이 같다면 점수가 증가하는 순으로 알아서 정렬된다.

 

그리고 해당 날짜에 할 수 있는 과제들을 저장할 can 리스트를 만들고,

첫 날짜를 가장 큰 마감일 날짜로 지정했다.

 

date를 줄이면서 해당 날짜에 할 수 있는 과제를 can 리스트에 넣고

다 넣은다음엔 정렬한다.

(사실 이 과정은 비효율적이라고 생각해서 우션순위 큐를 사용한다면 더 직관적일 것이라고 생각한다.)

 

처음에는 막연하게 date 날짜가 0이 된 경우 (즉 숙제를 할 수 있는 기간이 끝난경우)

그리고 더 이상 남아있는 숙제가 없는 경우에는 반복문을 종료하면 될 거라고 생각했다.

 

종료를 해야하는 상황은 잘 생각했지만, 문제는 종료 시점이었다.

위와같이 코딩한다면 다음과 같은 특이 상황에서 정답을 구하지 못한다.

 

3

3 30

3 30

3 30

 

최댓값은 90이지만, 이 코드는 30을 출력한다.

맨 처음 can 배열에 숙제를 담을때 저 3개를 모두 담아버리니 더 이상 남은 숙제가 없는 것으로 인식된 것이다.

그러나 can배열에는 숙제가 남아있고, 기한도 남아있으니 아직 과제를 더 할 수 있다.

 

다음과 같이 종료 시점을 바꾸어 통과했다.

# 13904 과제
import sys
n = int(input())
homeworks = []
for _ in range(n):
    deadline, score = map(int, sys.stdin.readline().split())
    homeworks.append((deadline, score))
homeworks.sort()
can    = []
date   = homeworks[-1][0]
answer = 0
while True:
    if date == 0:
        break
    while homeworks and homeworks[-1][0] >= date:
        can.append(homeworks.pop()[1])
    date -= 1
    if not can:
        continue
    can.sort()
    answer += can.pop()
print(answer)

전체 반복문의 종료 시점은 오직 더 이상 숙제를 할 시간이 없을 때로 정해두고,

그때 그때 숙제를 뽑을 수 있을 때는 다 뽑는다.

 

이렇게 알고리즘을 짜면, can 배열이 남아있고, 기한이 남아있는 한

과제를 풀면서 점수를 얻게 된다.

---

보통 문제를 풀었을 때, WA를 받게되면, 일반적인 케이스는 어느정도 맞으나

특이한 케이스에서 걸려서 안되는 경우가 많았다.

그 중 특이한 케이스의 경우가 '경계값'인 경우가 매우 많았던 기억이 남았다.

그래서 항상 경계값을 넣어보곤 한다.

 

입력값의 범위가 A <= X <= B 일 때

보통은 B의 값이 매우 크기때문에 이때는 경계값을 잡아 테스트 하기가 힘들지만,

A값은 경계값을 잡아 테스트하기 좋다. 그래서 이 값을 넣으면서 테스트를 한다.

 

그러나 이 문제를 통해 알게된 경계는 일종의 '구성의 경계' 였다.

여러 종류의 데이터가 들어올 때, 한 종류의 데이터만 들어오는 경우를 테스트 하지 않은 것이다.

 

13904 과제 문제의 경우 다양하게 테스트를 할 수 있다.

 

한 종류의 기한으로 여러개의 과제가 오는 경우

- 이때 점수가 한 종류 인경우

- 이때 점수가 증가하는 순인경우

-이때 점수가 감소하는 순인경우

-이때 점수가 랜덤인 경우

한 종류의 기한으로 1개의 과제만 오는 경우

 

여러 종류의 기한으로 여러개의 과제가 오는 경우

- 이때 점수가 한 종류 인경우

- 이때 점수가 증가하는 순인경우

-이때 점수가 감소하는 순인경우

-이때 점수가 랜덤인 경우

 

나는 값(점수)에만 집중하여 점수의 경계값과 점수가 한종류 일 때와 같은 상황만 체크했던 것이 놓친 점이었다.

하나의 관점을 고정해놓고 다른 관점을 변화 시켜가면서 체크하는 습관을 들이는 것이 좋겠다.