[Python] 백준 18234번 - 당근 훔쳐 먹기

문제 https://www.acmicpc.net/problem/18234

18234번: 당근 훔쳐 먹기

 

예제는 잘 돌아가는데 시간초과가 나서 며칠동안 고군분투했던 문제..

그냥 문제가 귀여워서 재밌어 보이길래 시도한 건데 푼 사람도 많이 없어서 구글링해도 시간초과 해결하는 법을 찾을 수 없었다.. 같이 스터디하는 친구도 시간초과 났었는데 해결한 후 본인 알고리즘 설명해준 거 듣고 나도 비슷한 방식으로 접근해봤다.

---

우선, 당근 맛의 최댓값을 가지려면 t-n일 동안은 당근을 훔쳐 먹지 않아야 한다.

t-n+1일부터 n일 동안 하루에 하나씩 훔쳐 먹는다.

 

1. 2차원 배열 carrot 리스트에 w, p를 입력 받기. #w: 당근 기본 맛, p: 영양제
2. greedy를 사용하여 풀어야 하므로 영양제의 효과(p)를 기준으로 오름차순 정렬.
3. 하루에 한 번 영양제를 넣어주므로 n일까지는 n-1번 영양제를 넣는다.
4. n일 동안 i에 대한 for문을 역순으로 돌려서, 현재 가장 영양제 효과가 큰 당근의 기본 값 w + 매일 넣는 영양제 p*(t-n+i)를 더해준다.
5. 훔쳐 먹고 나면 당근이 없으므로 .pop()을 통해 당근을 제거해주어야 한다.

---

2번 과정에서 리스트의 다중 조건 정렬을 하기 위해 lambda를 사용했다.

이거에 대해서는 따로 정리해서 글을 써야겠다.

2021.07.09 - [Python] - lambda를 사용한 정렬

 

전에는 이중 for문을 사용해서 시간 초과가 난 것 같다.

2021.07.07 - [HUFS/HUFS 모각코 캠프] - 210707 Today I Learned (시간 초과 났던 코드들)

w, p를 리스트 하나로 받고, lambda 사용하니까 이중 for문을 안 쓸 수 있었다.

이중 for문 안 쓰는 게 항상 난관인 것 같아 :(

 

알고리즘을 말로 설명하기가 어려워서.. 다음에 다시 보게 되면 이해할 수 있을까 싶긴하다.

오히려 코드만 보면서 이해하는 게 더 쉬울 것 같기도 ㅋㅋ

쨌든, 시간제한 1초는 너무하다.

 

import sys
n, t = map(int, sys.stdin.readline().split()) #n:당근 종류, t:재배일수

#carrot = [[w, p]] (w: 당근 기본 맛, p: 영양제)
carrot = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
carrot.sort(key = lambda x:(x[1], x[0]))
total_w = 0

for i in range(n-1, -1, -1):
    total_w += carrot[-1][0] + carrot[-1][1]*(t-n+i)
    carrot.pop()
print(total_w)

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ눈물난다