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

문제 링크

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

문제 설명

• 10~0점 존재
• k점에 쏜 화살이
  • 라이언 > 어피치일 경우 라이언이 k점 얻음
  • 라이언 <= 어피치일 경우 어피치 k점 얻음
• 어피치가 화살을 쏜 결과가 주어질 때
• 라이언이 가장 큰 점수차로 이기는 경우를 리턴
• 그 점수 차가 여러개인 경우 가장 낮은 점수를 더 많이 쏜 경우를 리턴
• 가장 낮은 점수가 같을 경우 그 다음 낮은 점수를 더 많이 쏜 경우를 리턴

풀이

재귀 구현

• 마지막 점수일 경우(0점) 다 쏨
• 현재 점수에서
  • 이길 수 있을 경우
    • 이기거나 -> 어피치보다 1개 더 많이 쏨
    • 지거나 -> 안 쏨
  • 이길 수 없을 경우 -> 안 쏨
• 모두 검사했을 경우( i == 11 일 때 종료 조건)
  • 이겼을 경우 갱신, 경우의 수 모두 저장

재귀 호출 이후

• 갱신 한 번도 안됐으면 [-1] 리턴
• 갱신 됐으면 저장한 모든 경우의 수를 검사
  • 가장 낮은 점수 더 많이 쏜 경우 리턴
  • 같으면 그 다음 경우 리턴

후기

• 굉장히 애먹었다
• 일단 재귀 구현도 애먹었다
• 점수 차이를 계산해야하는데 라이언의 고득점으로 생각 ㅜ
• 점수 차이가 같을 경우에도 계속 갱신해주면, 자동으로 낮은 점수를 많이 쏜 경우가 결과로 나올거라고 생각했는데, 모든 결과를 직접 비교해야했다.

코드

import copy
info = []
currArrow = [0] * 11
maxArrow = [-1]
maxDiff = float("-inf")

def solution(n, infoo):
    global info
    info = infoo
    
    updateArrow(0, n)
    
    if maxDiff == float('-inf'):
        return [-1]
    
    maxrow = maxArrow[0]
    for i in range(1, len(maxArrow)):
        currrow = maxArrow[i]
        for j in range(10,-1,-1):
            if maxrow[j] == currrow[j]:
                pass
            if maxrow[j] < currrow[j]:
                maxrow = currrow
                break
            if maxrow[j] > currrow[j]:
                break             
    return maxrow


def updateArrow(i, remains):
    global maxArrow, maxDiff
    
    if i == 11:
        diff = getDiff()
        if diff <= 0:
            return
        if maxDiff < diff:
            maxDiff = diff
            maxArrow = [copy.deepcopy(currArrow)]
        elif maxDiff == diff:
            maxArrow.append(copy.deepcopy(currArrow))
        return
    
    if i == 10: # 0점
        
        currArrow[10] = remains
        updateArrow(11, 0)
        currArrow[10] = 0
    
    elif remains > info[i]:    # 가능할때
        
        currArrow[i] = info[i] + 1
        updateArrow(i+1, remains - (info[i]+1)) # 쏘거나
        
        currArrow[i] = 0
        updateArrow(i+1, remains) # 안쏘거나
    
    else:   # 불가능할때
        updateArrow(i+1, remains) # 안쏘거나
    

def getDiff():
    score1 = 0
    score2 = 0
    for i in range(11):
        if info[i] == 0 and currArrow[i] == 0:
            continue
        # 어피치 < 라이언
        if info[i] < currArrow[i]: 
            score2 += (10-i)
        # 어피치 >= 라이언
        else:
            score1 += (10-i)
    diff = score2 - score1
    return diff