[모각코] 210707 Today I Learned

백준 #18234 당근 훔쳐 먹기

18234번: 당근 훔쳐 먹기 (acmicpc.net)

18234번: 당근 훔쳐 먹기

n, t = map(int, input().split())    # 당근 종류, 일수
w = []  # 맛
p = []  # pi만큼 맛 증가
for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    p.append(b)
    w[i] = w[i] + p[i] * (t-1)  # 마지막날 맛으로

eat = 0 # 토끼가 먹을 제일 맛있는 당근
max_eat = 0	# 토끼가 먹은 당근들 맛 합
'''for i in range(n):
    for j in range(n):
        if eat < w[j]:
            eat = w[j]
            c_kind = j   # 당근 종류 저장
        w[j] = w[j] - p[j]
    max_eat += eat
    del w[c_kind]
    del p[c_kind]
    eat = 0 # 먹을 당근 초기화'''

i = 0
while len(w) != 0:
    if eat < w[i]:
        eat = w[i]
        c_kind = i   # 당근 종류 저장
    w[i] = w[i] - p[i]

    if i == len(w)-1:   # 마지막 당근이면
        max_eat += eat
        del w[c_kind]
        del p[c_kind]
        eat = 0 # 먹을 당근 초기화
        i = 0
    else:
        i += 1

print(max_eat)

 

 

 

마지막 날을 기준으로 wi(당근 맛)가 가장 큰 값부터 거꾸로 선택해나가는 알고리즘을 생각했다.
t일날 wi가 가장 큰 값, t-1일날 wi-1이 가장 큰 값 ... 이렇게 마지막 날부터 wi가 큰 당근을 하나씩 선택해 나가는 것이다.
그래서 wi, pi input을 받을 때 wi 값에 t-1날만큼 pi를 더한 마지막 날의 최종 맛을 갱신해줬다.

그런데 시간초과가 난다,,, 왤까 ,,,, 이중 for문 없애서 될 줄 알았는데 생각해보니까 for문만 안 썼지 시간은 똑같이 걸릴 거 같음
내가 모르는 기법같은 게 있는 걸까 ㅠ
토요일에 다시 풀어봐야겠다....