[프로그래머스]양궁 대회

[51] 양궁 대회

책 구매하기

문제 정보

• 분류: 백트래킹
• 정답률: 33%
• 권장 시간 복잡도: O(2^M)
• 핵심 키워드: 백트래킹, 점수 차, 분배, 동점 우선순위
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/92342

문제를 읽을 때 체크할 포인트

점수를 몇 발에 배분할지 전부 훑어보는 문제다. 탐색 자체보다 동점일 때 낮은 점수를 더 많이 맞힌 배열을 우선하는 비교 규칙을 놓치지 않는 게 더 중요하다.

한 번의 선택으로 답이 확정되지 않고, 가능한 경우를 조건에 맞게 잘라 가며 끝까지 봐야 하는 유형이다. 그래서 '무엇을 상태로 들고 갈지'를 먼저 정하는 게 중요하다.

풀이 흐름

1. 0점부터 10점까지 각 점수 칸에 화살을 쏠지 말지 재귀로 결정한다.
2. 모든 분배가 끝나면 라이언과 어피치 점수를 계산한다.
3. 최대 점수 차를 갱신하고, 동점이면 우선순위 규칙으로 배열을 비교한다.

구현할 때 놓치기 쉬운 부분

점수 차가 같을 때는 낮은 점수 과녁을 더 많이 맞힌 배치를 우선한다. 최댓값만 갱신하고 이 보조 조건을 빼먹으면 정답 배열이 달라진다.

파이썬 정답 코드

def solution(n, info):
  # 0점부터 10점까지 각 점수 칸에 화살을 쏠지 말지 재귀로 결정한다.
  best_diff = 0
  best = [-1]

  def better(a, b):
    for i in range(10, -1, -1):
      if a[i] != b[i]:
        return a[i] > b[i]
    return False

  def score_gap(arr):
    lion = apeach = 0
    for i in range(11):
      score = 10 - i
      if arr[i] == 0 and info[i] == 0:
        continue
      if arr[i] > info[i]:
        lion += score
      else:
        apeach += score
    return lion - apeach

  def dfs(idx, remain, arr):
    nonlocal best_diff, best

    if idx == 11:
      arr[10] += remain
      diff = score_gap(arr)
      if diff > 0:
        if diff > best_diff or (diff == best_diff and better(arr, best)):
          best_diff = diff
          best = arr[:]
      arr[10] -= remain
      return

    need = info[idx] + 1
    if need <= remain:
      arr[idx] = need
      dfs(idx + 1, remain - need, arr)
      arr[idx] = 0

    dfs(idx + 1, remain, arr)

  dfs(0, n, [0] * 11)
  # 모든 분배가 끝나면 라이언과 어피치 점수를 계산한다.
  return best

시간 복잡도

M은 점수 칸 개수 11이다.

각 점수 칸에 화살을 두는 경우와 두지 않는 경우를 상태로 보면 선택 경우의 수가 부분집합 규모로 불어난다. 점수 칸 수를 M이라 두면 최악의 경우 O(2^M)이다.

따라서 시간 복잡도는 O(2^M)이다.