백준_11508 (2+1세일_실버4_그리디)

• 링크 : https://www.acmicpc.net/problem/11508

---

메모

메모한 것

• 쉬운 내용임

알고리즘

while 등을 돌리고
    # 전처리
    3개 이하면 += sum()하고 continue
    
    아니면
    3개끼리 정렬해서 += [0]+[1]

---

내가 푼 - 답이 아니다??

• 나는 3개씩 끊어서 sort()를 수행했는데 <-- 여기서 틀리게 된듯
  • 이유 밑에 있음

''' 내가 푼 - 왜 정답이 아니지?? '''
arr = [int(input()) for _ in range(int(input()))]
cnt = 0
lst = []
ans = 0
for i in arr:
    cnt += 1
    lst.append(i)
    
    if cnt == 3:
        lst.sort(reverse=True)
        ans += (lst[0]+lst[1])
        cnt = 0
        lst = []
# 마지막으로 남은 쩌리들 += sum() 해서 넣고
ans += sum(lst)
print(ans)

블로그 - 답

• 나랑 똑같긴 한데 이게 정답인 이유

  • 최소비용을 구해야 하므로, 최대한 비싼 가격을 무료로 받기 위해
    입력받은 값들을 내림차순으로 정렬해줘야 한다
  • 나머지 내용은 내가 생각한거랑 같다

• 근데 왜인가 싶긴 함 뭐가 다르지???

• 참고링크1 : https://unie2.tistory.com/695

• 참고링크2 : https://hello70825.tistory.com/260

arr = [int(input()) for _ in range(int(input()))]

arr.sort(reverse=True)

cnt = 0
ans = 0

for i in arr:
    cnt += 1        
    if cnt == 3:   # 하나씩 꺼내서 3번째면 PASS
        cnt = 0
    else:
        ans += i   # 하나씩 꺼내서 3번째가 아닌 수만 더해준다
print(ans)