백준 18234 당근 훔쳐 먹기

 

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

 

18234번: 당근 훔쳐 먹기

 

시험기간이지만 알고리즘을 풀고 싶었다,, 사실 CS 재미도 없고 하기 싫어서 풀었다

ㅎㅎ,, 죄송합니다

출처

 

다 읽고 해결과정 노트에 적고 '어.. 이거 쉽게 풀겠는데? 왜 골3이지' 이 생각 했는데 시간초과

📌 해결순서 

 

2번째 예시를 이용하면 파란색 동그라미를 친 7 + 24 + 38 = 69 가 토끼가 먹을수 있는 당근의 맛 최대 합이다.

토끼는 (총 재배일 수) - (당근의 종류) + 1 날짜부터 당근을 뽑아 먹어야 최대로 먹을수 있음을 알 수 있다.

 

이제 이걸 코드로 구현해야 했는데, 

처음에는 반복문을 계속 돌면서 당근의 맛을 업데이트 한 후 min 함수를 사용해서 현재 남아있는 당근중 가장 맛의 값이 작은 당근을 뽑아 먹은후 그 자리를 sys.maxsize 로 변경해 주는 식으로 풀었다(이렇게 하면 다음 반복문을 돌때 min 함수의 출력값으로 나올 수 없음) 

와 풀었다! 하고 제출 했는데 와 시간초과였다!

반복문을 돌때마다 min 함수를 호출하고 index 함수도 계속 호출 했기 때문에 시간초과가 나올 수 밖에 없다. 제출하려고 했을 때 제한시간 1초인거 보고 삘이 왔었다,,,ㅎ 

heap 우선순위 큐를 사용해서 토끼가 당근을 뽑아 먹을때마다 pop 을 해줄까도 생각해 봤지만 그렇게 되면 큐 안에서 당근의 위치가 계속 변하게 되고 변할때 마다 그 위치를 파악해줘야 한다. 다음 반복문에서 또 영양제의 값 만큼 맛을 더해줘야 하기 때문에,, 그래서 이건 아니라고 생각했다.

 

📌 코드(시간 초과)

import sys

input = sys.stdin.readline

carrots_type, harvest_day = map(int, input().split())
taste_list = [list(map(int, input().split())) for _ in range(carrots_type)]
carrots_list = [0] * carrots_type

start_day = harvest_day - carrots_type

taste_sum = 0


for day in range(harvest_day):
    if day == 0:
        for i in range(len(taste_list)):
            carrots_list[i] = taste_list[i][0]
    else:
        for i in range(len(taste_list)):
            carrots_list[i] += taste_list[i][1]

    if day >= start_day:
        target_carrot = min(carrots_list)
        taste_sum += target_carrot
        index = carrots_list.index(min(carrots_list))
        carrots_list[index] = sys.maxsize

print(taste_sum)

이 문제는 그리디 방식으로 접근하면 굉장히 쉽게 풀 수 있다.

위에서 그린 표에서 볼 수 있듯이 토끼가 당근을 먹는 순서는 당근을 더 맛있게 할 수 있는 영양값의 오름차순으로 먹는다

영양제가 3인 밭, 7인 밭, 9인 밭 순으로

당근을 더 맛있게 만들 수 있는 기준은 영양제의 값이 얼마나 큰가이다.

 

그래서 반복문 돌기전에 영양제의 값 기준으로 sort 해줬다!

 

그리디를 풀면서 느끼는 건데, 뭔가 딱 한번의 반복을 통해서 정답을 구할 수 있게끔 문제의 조건들을 잘 활용해서 자료구조를 변경 한다던가, 순서를 변경 한다던가 자료구조를 하나 더 만들어준다던가,, 등등을 미리 해주면 항상 편하게 풀었던 것 같다.

그렇다면 앞으로 그리디 문제를 만났을 때 생각해봐야 할 점은 문제에서 준 조건을 활용해서 자료구조를 건드려야 하는 문제인지, 아니면 생으로 그리디 방식으로 판단해서 해결해나가야 하는 문제인지를 잘 판단해야 한다는 것. 

 

그나저나 오리 귀엽다..ㅎ

📌 코드 

import sys

input = sys.stdin.readline

carrots_type, harvest_day = map(int, input().split())
taste_list = [list(map(int, input().split())) for _ in range(carrots_type)]
taste_list.sort(key=lambda x: (x[1], x[0]))

eat_day = harvest_day - carrots_type
taste_sum = 0

for taste in taste_list:
    current_taste, add_taste = taste[0], taste[1]
    taste_sum += current_taste + add_taste * eat_day
    eat_day += 1

print(taste_sum)