[모각코] 210707 Today I Learned

그리디 알고리즘 공부

2021.06.29 - [HUFS/Algorithm] - Greedy Algorithm (그리디, 욕심쟁이 알고리즘)

Greedy Algorithm (그리디, 욕심쟁이 알고리즘)

 

 

 

<백준 18234번 - 당근 훔쳐 먹기>

예제는 맞는데 시간 초과가 난다. 이중 for문을 사용해서 그런 것으로 추정되는데 이중 for문 안 쓰고 푸는 방법이 도무지 생각나지 않는다.

코드 길이라도 줄여보려고 다른 방식으로 코드를 하나 더 작성했으나 이것도 이중 for문을 사용해서인지 시간 초과가 났다.

나름 그리디로 푼다고 풀은 건데, 시간복잡도 줄여야 한다는 생각에 나중에는 그냥 막 짠 것 같다. ㅋㅋ

어쨌든 결과적으로 틀린 코드라서 올릴까 말까 고민하다가... 나중에 나도 다시 봐야 하고, 혹시나 누군가 이걸 보고 ... 나에게 피드백을 줄 수도 있지 않을까.. 하는 마음에 올린다.

 

 

#처음에 만든 코드

import sys

n, t = map(int, sys.stdin.readline().split()) #n:당근 종류, t:재배일수
w = [0 for i in range(n)] #당근 기본 맛
p = [0 for i in range(n)] #영양제
for i in range(n):
    w[i], p[i] = map(int, sys.stdin.readline().split())

total_w = 0 #맛의 합
for i in range(1, t+1):
    if i <= t-n: #t-n일 전까지는 당근 훔쳐먹지 x
        for j in range(n):
            w[j] += p[j]
    elif i == t: #마지막 날
        total_w += w[0]
    else:
        min_p = min(p) #영양제로 인해 증가하는 값이 가장 적은 경우
        index = p.index(min_p)
        total_w += w[index]
        w.remove(w[index])
        p.remove(min_p)
        for j in range(len(w)):
            w[j] += p[j]
    
print(total_w)

 

 

#시간복잡도 줄여보겠다고 다시 만든 코드

import sys
n, t = map(int, sys.stdin.readline().split()) #n:당근 종류, t:재배일수
w = [0 for i in range(n)] #당근 기본 맛
p = [0 for i in range(n)] #영양제
for i in range(n):
    w[i], p[i] = map(int, sys.stdin.readline().split())

total_w = 0 #맛의 합
for j in range(n):
    w[j] += p[j]*(t-1)
for i in range(t, 0, -1):
    max_w = max(w)
    total_w += max_w
    index = w.index(max_w)
    w.remove(max_w)
    p.remove(p[index])
    if i == t-n+1:
        break
    else:
        for j in range(len(w)):
            w[j] -= p[j]
print(total_w)

 

 

---

풀었다 !

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