Hey Tech
그리디(Greedy) 알고리즘 백준#12845 #실버 | "모두의 마블" | 파이썬 풀이 본문
728x90
반응형
문제
문제 원본: https://www.acmicpc.net/problem/12845
접근법
가장 높은 골드를 획득하는 방법, 간단합니다.
레벨이 가장 높은 카드 1장을 고정하고 나머지 카드와 차례로 덧셈하면 됩니다.
어차피 모든 카드의 레벨과 합산해야 하며,
두 카드의 덧셈이(=획득 골드량) 최대가 되기 위해서는 최상위 레벨의 카드 1장을 고정시키면 되는 것이죠.
소스코드
# 카드 개수 입력받기
n = int(input())
# 카드별 레벨 입력받기
level_list = list(map(int, input().split()))
# 카드 레별에 따라 내림차순 정렬
level_list.sort(reverse= True)
# 획득할 골드 초기화
answer = 0
# 가장 큰 레벨 카드 2장 합산
answer += level_list[0] + level_list[1]
# 레벨 큰 순서대로 카드 합산
for i in range(2, n):
answer +=level_list[0] + level_list[i]
print(answer)
레벨에 따라 카드를 내림차순으로 정렬했기 때문에 최상위 레벨의 카드는 [0] 인덱스 요소입니다.
해당 원소를 고정하고 나머지 카드와 한 번씩 더해 나가면 정답이 됩니다.
시간 복잡도: O(N)
하나의 카드는 고정되고 나머지 카드 1장씩 더해지는 연산을 총 (N-1)번 반복하므로 시간 복잡도는 O(N)입니다.
더 좋은 아이디어가 있으시거나 포스팅 내용에 오류가 있다면 아래에 👇👇👇 댓글 남겨주세요!
그럼 오늘도 건강하고 즐거운 하루 보내시길 바랍니다 :-)
고맙습니다.
728x90
반응형
'알고리즘 > 문제풀이' 카테고리의 다른 글
BFS 알고리즘 | 백준#17086 #실버 | "아기상어2" | 파이썬 풀이 (0) | 2021.08.24 |
---|---|
BFS 알고리즘 | 백준#11123 #실버 | "양 한 마리, 양 두 마리" | 파이썬 풀이 (2) | 2021.08.20 |
그리디(Greedy) 알고리즘 백준#1202 #골드 | "보석 도둑" | 파이썬 풀이 (0) | 2021.08.19 |
그리디(Greedy) 알고리즘 백준#11047 #실버 | "동전 0" | 파이썬 풀이 (0) | 2021.08.18 |
[알고리즘] 그리디(Greedy) 알고리즘(거스름돈 문제 소스코드) (0) | 2021.02.22 |