Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- Stack
- 구현
- 적정 스레드
- springboot
- g1gc
- 분할정복
- 브루트포스
- 몬티홀
- 문제풀이
- 정수론
- Python
- GC
- BFS
- 배열 돌리기1
- 그래프탐색
- github
- 빌더패턴
- 마크다운
- deque
- Markdown
- Greedy
- 그리디
- GarbageCollector
- 회고
- 프로세스
- 이진탐색
- 면접복기
- 그래프 탐색
- 백준
- DP
Archives
- Today
- Total
FeelingXD
[백준 - 31589] 포도주 시음 🍷 본문
❓ Problem
🤔 How
어떤경우에 포도주로 최고의 만족감을 얻을수 있을까 Greedy 하게 접근해보자. 😀
구현 로직
- 우선 탐욕법으로 접근하기위해 포도주가 순서대로 정렬되어있어야한다.
- 포도주 에서 마실수있는 최고의 포도주를 마신다.
- 남은 포도주 에서 최저의 만족감을 주는 포도주를 마신다. (이미 최고의 포도주를 마신 뒤이므로 효용은 0이다.)
- 2->3 을 반복한다.
🍷 최적해를 찾아 탐욕적으로 접근하기 포도주에서는 어떻게 작동할까
- 우선 포도주에서 마실수있는 최고 효용을 K 라고 했을때 첫잔에서 얻을수있는 최고만족감은 언제나 K이다.
- 그후 남은 포도주에서 마실수있는 최저의 효용을 얻는다. 이때 얻을수있는 만족 효용은 0이다.
- 남은 포도주중에서 최고 효용의 포도주를 마신다. 이때 얻을 수 있는 효용은 현재마신 포도주 - 이전에 마신 포도주이다.
이를 반복하면서 탐욕적으로 접근할 수 있다.
❗ Solve
# 포도주 시음
import sys
input = sys.stdin.readline
def solution():
N, K = map(int, input().split()) # 갯수와 ,주량
wines = [0] + list(map(int, input().split()))
wines.sort()
prev = 0
end = len(wines) - 1
cnt = 0
ans = 0
while cnt < K:
if cnt % 2:
prev += 1
cnt += 1
else:
ans += wines[end] - wines[prev]
end -= 1
cnt += 1
print(ans)
pass
if __name__ == "__main__": # 실행되는 부분
solution()
pass
'프로그래밍 > 문제풀이' 카테고리의 다른 글
[프로그래머스 - 131120] 3월에 태어난 여성 회원 목록 출력하기 📃 (0) | 2024.03.14 |
---|---|
[백준 - 4963] 섬의 개수 🐢 (0) | 2024.03.14 |
[프로그래머스 - 284531] 노선별 역 사이 거리 조회하기 🐢 (0) | 2024.03.13 |
[프로그래머스-42895 ] N으로 표현 🔑 (0) | 2024.03.09 |
[백준-1074] Z ✨ (0) | 2024.02.28 |