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 |
Tags
- python
- 다이나믹 프로그래밍
- dict
- DP
- level0
- 그리디
- dfs
- BOJ
- 코딩테스트
- 구현
- BFS
- 운영체제
- 딕셔너리
- 프로그래머스
- programmers
- N과M
- 브루트포스
- 수학
- 힙
- 파이썬
- 가상메모리
- 스택
- MYSQL
- 재귀
- level2
- level1
- 백준
- level3
- 다익스트라
- 가상메모리 관리
Archives
- Today
- Total
동캄의 코딩도장
프로그래머스 level2 [디펜스 게임] 파이썬 본문
https://school.programmers.co.kr/learn/courses/30/lessons/142085
#프로그래머스 level2 디펜스 게임
import heapq
def solution(n, k, enemy):
answer = 0
i=0
heap=[]
len_enemy=len(enemy)
while True:
# print(n,enemy[i])
if i==len_enemy:
return len_enemy
if n>=enemy[i]:
heapq.heappush(heap,-enemy[i])
n-=enemy[i]
else:
if k>0:
if heap:
M=-heapq.heappop(heap)
if M<enemy[i]:
heapq.heappush(heap,-M)
k-=1
i+=1
continue
n+=M
k-=1
continue
else:
k-=1
i+=1
continue
else:
break
i+=1
return i
처음에는 재귀를 통해서 문제를 해결하려고 하였으나, 당연하게도 시간초과가 발생하였다.
코드를 변경해 그리디로 해결하였다.
알고리즘은 다음과 같다.
1. n이 현재 적(enemy[i])보다 크거나 같으면 현재 적을 처리한다. (n=n-enemy[i])
2. n보다 현재 적이 더 크면
2-1) k가 0보다 큰 경우: 처음 적~ 현재 적까지중 가장 많은 수의 적이 있는 라운드에 무적권을 사용한다.
2-2) 없으면 현재 라운드를 반환한다.
3) 모든 라운드에서 생존하면 그 길이를 반환한다.
'코테 > 프로그래머스' 카테고리의 다른 글
프로그래머스 level1 [추억 점수] 파이썬 (0) | 2023.04.24 |
---|---|
프로그래머스 level2 [순위 검색] 파이썬 (0) | 2023.04.17 |
프로그래머스 level2 [연속된 부분 수열의 합] 파이썬 (0) | 2023.04.14 |
프로그래머스 level2 [시소 짝꿍] 파이썬 (0) | 2023.04.14 |
프로그래머스 level2 [요격 시스템] 파이썬 (0) | 2023.04.14 |