문제 링크

해결 과정

• 최대한 라운드를 길게 끌기 위해서는 다음 순위에 맞게 행동해야 합니다.
  • 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

유사 문제

제가 생각했을 때, 해당 그리디 알고리즘과 비슷한 문제는 아래와 같습니다.

• 디펜스 게임