[백준 18234번] 당근 훔쳐 먹기(파이썬)

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

18234번: 당근 훔쳐 먹기

이 문제를 처음 딱 접하면

어라???쉬운데?

라는 생각이 드실 수 있습니다.

 

처음에 문제를 마주할 때 생각은

토끼가 매일마다 당근을 훔쳐먹으니

매일 당근 중 최대를 찾아

먹고 튀는 걸로 계산할 수 있겠다는 생각입니다.

그런데, 이 문제는 그렇게 풀면 큰 코 다칩니다.

저런 아이디어를 코드화해서

예제1을 입력하면

어라? 왜 6이 나오지??

예제1 출력은 8이 나와야하는데...

 

왜 6이 나오냐

처음에 당근밭에 당근이 없으니

당근을 추가해줍니다.

그럼 당근밭에는 3과 1이 있네요.

이때 당근 최대가 3이니 3을 먹습니다.

그리고 그 다음에는 3을 새로 심고(이미 먹었으니)

1은 영양제를 줘서 3으로 키웁니다.

그럼 최대가 또 3이니

3+3=6이 되버립니다.

 

그런데 문제에서 요구한 건 그게 아닙니다.

1일차에는 1을 먹고

2일차에는 기다렸다가 7을 먹는 겁니다.

 

이걸 어떻게 구현하지 하다가

예제 3을 기준으로 그림을 그려봤습니다.

여기서 핵심은

'당근을 가능한 최대로 키워서 먹는다'라는 것이었습니다.

처음에 1이었던 당근은

T-1시간이 지나면 91로 최대가 됩니다.

그럼 이 당근은 가장 마지막에 먹으면 되겠네요?

그전에 T-2시간에는 83이 된 당근을 먹고.

이런 식으로 쭉 역추적하는 겁니다.

이렇게 생각이 가능한 건

'토끼가 당근을 안 먹을 수도 있다'라는 조건 때문입니다.

토끼가 당근을 먹으러 갔다가

'존버했다가 더 맛있어지면 먹어야지'

라고 할 수 있습니다.

 

"""
#당근을 최대한 키운다는 전재로 가본다
for i in range(1,N+1):
    room[i]+=ca[i][1]*(T-1)


#역으로 본다
#당근을 계속 키웠을 때의 최대부터 계속 빼준다
while True:
    if room.count(0)==N+1:
        break

    tasty=max(room)
    eat=room.index(tasty)
    rabbit+=tasty
    room[eat]=0

    for i in range(1,N+1):
        if room[i]==0:
            continue
        room[i]-=ca[i][1]

print(rabbit)
"""

이걸 바탕으로 초기에 구현한 코드입니다.

이 코드는 아쉽게도 pypy3로도 시간초과가 났습니다.

반복문을 T만큼 돌면서

배열을 또 N만큼 탐색하니

T*N의 시간이 필요.

T와 N의 값이 커질 수록

시간복잡도가 증가하기 때문입니다.

그래서 당근을 영양제 순으로 정렬한 후

각각을 최대로 먹을 수 있는 케이스로 다시 구성했습니다.

 

#백준 18234번 당근 훔쳐 먹기

N,T=map(int,input().split())
ca=[]

for i in range(N):
    w,p=map(int,input().split())
    ca.append([w,p])
ca.sort(key=lambda x:x[1])
ca.reverse()

day=T-1
rabbit=0

for i in range(N):
    eat=ca[i][0]+(ca[i][1]*day)
    rabbit+=eat
    day-=1

print(rabbit)

https://lagooni.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-18234%EB%B2%88-%EB%8B%B9%EA%B7%BC-%ED%9B%94%EC%B3%90-%EB%A8%B9%EA%B8%B0

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

아이디어에 도움을 준 글도 같이 첨부합니다.

 

이 문제는 여러모로 아이디어 관점에서

학습할 것이 많은 문제입니다.

꼭 제대로 숙지하셔서

그리디 알고리즘에 대비하시면 좋을 것 같습니다.