문제 링크
해결 과정
•
최대한 라운드를 길게 끌기 위해서는 다음 순위에 맞게 행동해야 합니다.
◦
1순위: 내가 가지고 있는 카드 뭉치에서 두 장을 소모해서 목표 숫자를 만들기
◦
2순위: 내가 가지고 있는 카드 뭉치에서 한 장을 소모 + 새로 뽑은 카드 중 한 장을 이용
▪
동전 1개 추가 소모
◦
3순위: 새로 뽑은 카드 두 장을 모두 소모하여 목표 숫자를 만들기
▪
동전 2개 추가 소모
◦
결과적으로, 최대한 동전을 쓰지 않는 방향으로 게임을 진행해야 합니다.
•
하지만, 해당 그리디 알고리즘을 그대로 사용할 경우, 입출력 예시로 주어진 라운드를 달성할 수 없습니다.
•
따라서, 약간의 전략 수정이 필요합니다.
•
바로 현재까지 뽑은 카드 정보를 별도의 공간에 기록하고, 필요한 순간에 뽑았던 카드를 소모하는 전략입니다!
◦
step 1) 라운드를 진행할 때마다, 딕셔너리에 새로 뽑은 두 개의 카드 번호를 저장 → 검색 시간 복잡도를 O(1)로 만들기 위함
◦
step 2) 내가 가지고 있는 카드 뭉치 / 동전 / 새로 뽑은 카드 목록을 확인하여 몇 순위의 행동을 할 지 확인
◦
step 3) 순위에 해당하는 action을 수행
•
이렇게 전략을 변경하면, 기존 게임 규칙을 어기지 않으면서 최적의 결과를 구할 수 있습니다.
전체 코드
def check_available(remain_cards: dict, picked_cards: dict, target_num: int):
for num in remain_cards.keys():
if target_num-num in remain_cards: # 동전을 안써도 되는 경우
return ('no_coin', [num, target_num-num])
for num in remain_cards.keys():
if target_num-num in picked_cards: # 동전 한 개를 사용해야 하는 경우
return ('one_coin', [num, target_num-num])
for num in picked_cards.keys():
if target_num-num in picked_cards: # 동전 두 개를 사용해야 하는 경우
return ('two_coins', [num, target_num-num])
return ('unavailable', None)
def solution(coin, cards):
answer = 1
current = int(len(cards) // 3) # 현재 위치
target_num = len(cards) + 1 # 타겟 숫자
remain_coins = coin # 현재 가지고 있는 동전 갯수
remain_cards = {num: 'ok' for num in cards[:current]} # 현재 가지고 있는 카드 목록
picked_cards = dict() # 현재까지 뽑은 카드 목록
while remain_cards and current < len(cards)-1: # 현재 카드를 가지고 있다면, 반복문 수행
for num in cards[current:current+2]: # 매 라운드마다 카드 두 장 뽑기
picked_cards[num] = 'ok'
flag, nums = check_available(remain_cards, picked_cards, target_num)
if flag == 'no_coin': # 동전을 안써도 되는 경우
for num in nums: # 원래 가지고 있던 카드를 제거
del remain_cards[num]
current += 2
answer += 1
elif flag == 'one_coin': # 동전 한 개를 사용해야 하는 경우
if remain_coins >= 1: # 낼 수 있는 동전이 있는 경우
del remain_cards[nums[0]]
del picked_cards[nums[1]]
remain_coins -= 1
current += 2
answer += 1
else: break # 낼 수 있는 동전이 없는 경우
elif flag == 'two_coins': # 동전 두 개를 사용해야 하는 경우
if remain_coins >= 2:
for num in nums: # 새로 뽑은 카드 목록에서 제거
del picked_cards[num]
remain_coins -= 2
current += 2
answer += 1
else: break # 낼 수 있는 동전이 없는 경우
else: # 다음 라운드를 갈 수 없는 경우
break
return answer
Python
복사
유사 문제
제가 생각했을 때, 해당 그리디 알고리즘과 비슷한 문제는 아래와 같습니다.
•
디펜스 게임