양궁대회

https://school.programmers.co.kr/learn/courses/30/lessons/92342

문제 접근

어피지 의 우승을 바라는 부패한(?) 양궁대회 위원회에 대해 라이언의 우승으로 정의를 실현하고자 하는 문제입니다.

라이언이 이기기 위한 조건

• 어피치 보다 1발 이상 맞췄을 때, 비로소 점수를 얻게 됩니다.
• 최종 점수가 어피치 점수보다 반드시 높아야 합니다. (같으면 안 됨)
• 라이언 이 어피치 가장 큰 점수로 이겨야 합니다.

입출력 값

• 입력: 어피치 가 과녁을 맞춘 기록
• 출력: 라이언 이 어피치 를 이기기 위해 맞춰야 하는 과녁기록

문제 쪼개기

• 순열 문제
  • 가장 큰 점수로 이긴다는 말은 화살의 개수 를 효율적으로 사용한다는 말
  • 다시 말해, 라이언 은 어피치 보다 1발 더 맞추거나 아예 안 맞추면 됩니다.
  • 따라서 총 10개의 과녁에 대해, 각 점수 판당 2 가지의 경우의 수를 줄세우는 단순 순열 문제 입니다.
• 완전탐색
  • 모든 순열의 경우의 수를 조사하여, 문제의 조건에 가장 적합한 경우를 찾을 것입니다.
  • 순열 문제이므로 DFS를 사용할 예정입니다.
• DFS
  • 정지 조건
    • 화살을 모두 사용
    • 모든 과녁을 다 맞추었을 때
  • 함수의 인자
    • info : 어피치 의 기록
    • level : 현재 쏘고 있는 과녁의 종류
    • history: 라이언 이 과녁을 맞춘 기록
    • score: 현재 점수
    • arrows: 화살의 개수
    • answer: 라이언이 어피치를 이길 모든 경우의 수 담는 배열

문제 풀이

다소 코드가 길어질 수도 있지만, 명확한 풀이를 위해 각각의 동작을 함수 로 쪼개어 작성했습니다.

메인코드

import copy
def solution(n, info):
   answer = []

   dfs(info, 0, [], 0, n, answer) # 아직 아무것도 쏘지 않았을 때
   if len(answer) == 0: return [-1] # 라이언이 어피치를 이기는 경우(answer)가 없을 때

   answer.sort(key = sortHistory) # 가장 낮은 점수를 더 많이 맞힌 경우
   answer.sort(key = sortDiff) # 라이언이 어피치를 가장 많은 점수 차로 이기는 경우

   [lionHistory, diff] = answer[0] # 위의 2개 조건에 대해 가장 우선순위가 높은 경우
   
   return lionHistory

라이언 화살 경우의 수 찾기 (DFS)

def dfs (info, level, history, score, arrows, answer):
   if arrows == 0: # 화살이 없을 때 정지
       zeroPad = [0] * (11 - level)
       newHistory = history + zeroPad # 남은 화살이 없으므로 나머지 과녁에는 전부 0으로 처리
       apeachScore = calApeachScore(newHistory, info) # 라이언의 기록에 대한 어피치의 점수

       if score > apeachScore: answer.append([newHistory, score - apeachScore]) # 라이언의 스코어가 어피치보다 클 때 -> answer에 기록
       return

   elif level == 10: # 1점까지 다 쐈을 때 정지
       history.append(arrows)
       apeachScore = calApeachScore(history, info)
     
       if score > apeachScore: answer.append([copy.deepcopy(history), score - apeachScore]) # 라이언의 스코어가 어피치보다 클 때 -> answer에 기록
       history.pop()
       return

   
   apeachNum = info[level]

   if arrows >= apeachNum + 1: # 해당 점수에 대해 라이언이 어피치 보다 1발 더 맞추는 경우
       history.append(apeachNum + 1)
       dfs(info, level + 1, history, score + 10 - level, arrows - apeachNum - 1, answer)
       history.pop()
     
   history.append(0) # 해당 점수에 대해 라이언이 아예 화살을 맞추지 않을 경우
   dfs(info, level + 1, history, score, arrows, answer)
   history.pop()

어피치 점수 계산

def calApeachScore(lion, apeach): # 라이언의 기록과 info로 어피치 점수 계산
   sum = 0
   for i in range(11) :
       if lion[i] <= apeach[i] and (lion[i] != 0 or apeach[i] != 0): sum += 10 - i
   return sum

화살 쏜 기록 (배열) 뒤집어서 숫자로 만들기

def swapHistory (history):  # 기록 배열을 뒤집고 숫자로 바꾸면 "가장 낮은 점수를 더 많이 맞힌 경우"를 구할 수 있다. [1,2,3] vs [1,1,1] -> 321 vs 111 
   newHistory = copy.deepcopy(history)
   newHistory.reverse()
   return int(''.join(map(str, newHistory)))

조건에 맞도록 화살 쏜 기록 정렬하기

def sortHistory(x): # 가장 낮은 점수를 더 많이 맞힌 경우
   [history, diff] = x
   return -swapHistory(history)
def sortDiff(x): # 라이언이 어피치를 가장 많은 점수 차로 이기는 경우
   [history, diff] = x
   return -diff # 점수차 오름차순

전체 코드

import copy
def solution(n, info):
   answer = []

   dfs(info, 0, [], 0, n, answer) # 아직 아무것도 쏘지 않았을 때
   if len(answer) == 0: return [-1] # 라이언이 어피치를 이기는 경우(answer)가 없을 때

   answer.sort(key = sortHistory) # 가장 낮은 점수를 더 많이 맞힌 경우
   answer.sort(key = sortDiff) # 라이언이 어피치를 가장 많은 점수 차로 이기는 경우

   [lionHistory, diff] = answer[0] # 위의 2개 조건에 대해 가장 우선순위가 높은 경우
   
   return lionHistory
def dfs (info, level, history, score, arrows, answer):
   if arrows == 0: # 화살이 없을 때 정지
       zeroPad = [0] * (11 - level)
       newHistory = history + zeroPad # 남은 화살이 없으므로 나머지 과녁에는 전부 0으로 처리
       apeachScore = calApeachScore(newHistory, info) # 라이언의 기록에 대한 어피치의 점수

       if score > apeachScore: answer.append([newHistory, score - apeachScore]) # 라이언의 스코어가 어피치보다 클 때 -> answer에 기록
       return

   elif level == 10: # 1점까지 다 쐈을 때 정지
       history.append(arrows)
       apeachScore = calApeachScore(history, info)
     
       if score > apeachScore: answer.append([copy.deepcopy(history), score - apeachScore]) # 라이언의 스코어가 어피치보다 클 때 -> answer에 기록
       history.pop()
       return

   
   apeachNum = info[level]

   if arrows >= apeachNum + 1: # 해당 점수에 대해 라이언이 어피치 보다 1발 더 맞추는 경우
       history.append(apeachNum + 1)
       dfs(info, level + 1, history, score + 10 - level, arrows - apeachNum - 1, answer)
       history.pop()
     
   history.append(0) # 해당 점수에 대해 라이언이 아예 화살을 맞추지 않을 경우
   dfs(info, level + 1, history, score, arrows, answer)
   history.pop()
def calApeachScore(lion, apeach): # 라이언의 기록과 info로 어피치 점수 계산
   sum = 0
   for i in range(11) :
       if lion[i] <= apeach[i] and (lion[i] != 0 or apeach[i] != 0): sum += 10 - i
   return sum
def swapHistory (history):  # 기록 배열을 뒤집고 숫자로 바꾸면 "가장 낮은 점수를 더 많이 맞힌 경우"를 구할 수 있다. [1,2,3] vs [1,1,1] -> 321 vs 111 
   newHistory = copy.deepcopy(history)
   newHistory.reverse()
   return int(''.join(map(str, newHistory)))
def sortHistory(x): # 가장 낮은 점수를 더 많이 맞힌 경우
   [history, diff] = x
   return -swapHistory(history)
   def sortDiff(x): # 라이언이 어피치를 가장 많은 점수 차로 이기는 경우
   [history, diff] = x
   return -diff # 점수차 오름차순

주의할 점

• 모듈화: 이 문제 처럼 조건이 복잡한 문제를 논리의 순서대로 일일이 구현하다 보면, 길을 잃게 될 수 있습니다. 따라서 문제를 풀기 전, 세세한 계획 보다는 함수 단위로 크게 크게 쪼개어 전체적인 흐름을 작성하고, 이 후에 세부적인 함수를 묘사하는게 좋을 것 같습니다. 😁