[백준] 과제 : 13904번 - Python

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

13904번: 과제

 

 

 

문제를 풀면서 몰랐던 개념

 

(1) [Python] 값이 0으로 채워진 배열 만들기

result = [ 0 for _ in range(1000)]

 

(2) while 문은 값이 0이 되면 false여서 반복문을 탈출한다. -> 꼭 True일 때만 반복하지 않아도 된다!

 

(3) [Python] swipe

: C언어랑 달리 두 값을 등호(=)를 두고 위치를 바꿔주기만 하면 두 값이 바뀐다.

one2ye, 20s = 20s, one2ye

 

 

 

문제의 접근 방법

 

- 마감일을 내림차순으로 정렬한 후, 점수가 높은 과제부터 해치우기

- 최대한 마감일에 가깝게 처리하기

- 비어있는 스케줄을 나타내는 (0으로 채워진) 배열을 선언하여 이 스케줄이 비어있으면(0이면) 이 날은 과제를 할 수 있다는 뜻이므로 점수를 저장하기

- 스케줄이 차있으면 하루씩 앞으로 가서 점수가 더 큰 값을 넣어주는 식으로 비교하기

 

 

 

내가 막혔던 부분

 

- 점수가 큰 순으로 정렬해야할 지, 마감일이 많이 남은 순으로 정렬해야할 지에 대해서만 생각했다 => 아이디어가 떠오르지 않았다.

- 마감일부터 먼저 많이 남은 순서대로 정렬한 다음 그 날 할 수 있는 과제들 중 점수가 가장 높은 것 순서대로 계산한다 => 실제로 구현하는 것에서 막혔다.

- 마감일이 같은 날에 더 높은 점수를 가진 과제가 있을 때 어떤식으로 처리해야하는 지 고민했다.

- 비어있는 스케줄을 선언한 배열에서 범위를 1000으로 설정하여 런타임 에러가 났었는데, 에러가 난 원인을 찾지 못해서 헤맸다.

- while문 안에서 어느 시점에서 탈출해야 할지(break), 그 시점을 찾지 못했다.

- 내림차순 정렬의 필요 여부에 대해서 고민했다.

 

 

 

문제 풀이 방법

 

이해하는데 오래 걸렸던 문제.

풀이는 주석으로!

 

 

 

소스코드

n = int(input())

score = [list(map(int, input().split())) for _ in range(n)]
# 마감 기한과 과제 점수를 공백을 두고 n번만큼 입력받아서 리스트 형태로 score에 저장

score.sort(reverse=True, key=lambda x:x[1])
# 점수를 기준으로(인덱스 1번째 요소) 내림차순 정렬

result = [ 0 for _ in range(1001)]
# 최대 1000일의 과제 -> 반복문은 range 미만으로 계산되기 때문에 1001로 설정!
# 런타임 에러 주의

for d, w in score:
# score 안의 두 요소 마감기한(d), 점수(w)

    if result[d] == 0:  	# 만약 result[d] 가 0 이라면 = 과제를 할 수 있는 날이라면
        result[d] = w   	# 그 날에 점수 추가 (0이었던 값을 점수로 바꿔주기)

    else:   			# 이미 다른 과제 점수가 들어있다면

        while d:    			# d만큼 while문 반복 (d가 0이되면 false 이기 때문에 탈출)
            if w > result[d]:   	# 만약 새로운 점수가 기존에 있던 점수보다 높다면
                result[d] = w  
                break   		# 그 값으로 바꿔주고 반복문 탈출

            d -= 1  			# 아니라면 d값을 1씩 감소시켜주기
            # 이 값을 감소시켜서 그 앞의 값들이랑 비교해서 현재 w가 result[d]보다 크다면 다시 바꿔주기
            # 위 과정을 반복해서 최대한 마감기한이 많이 남은 것들부터 시작해서
            # 최대 점수를 넣어줄 수 있다!
            
            
print(sum(result))
# 최대 점수들이 모여있는 리스트인 result의 합을 출력해주기