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

📘 문제

플랫폼: 프로그래머스
난이도: Lv2
유형: 그리디, 조합

 

🔗 문제 링크

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

프로그래머스

 

어피치와 라이언이 양궁 대회를 한다. 과녁은 10점부터 0점까지 있고, 매개변수로 라이언이 쏜 화살 갯수와 어피치가 쏜 화살 정보가 주어진다.

라이언이 어떻게 하면 어피치와 가장 큰 점수 차로 이길 수 있는지 구하는 문제이다.

 

🧠 접근 방법 및 풀이 과정

combination을 활용해서 모든 라이언이 화살을 n번 쏜 모든 경우에 대하여 계산했다.

여기서 수학적 개념이 조금 필요한데.. 나는 GPT의 도움을 조금 받았다😅

그래서 다음에 한번 더 풀어봐야 할듯

GPT에게는 파이 N개를 11명이 나눠서 먹는 경우의 수를 모두 구해달라고 했다!

➡️ 요 부분은 저도 아직 이해를 못해서 이해한 뒤 설명 첨부하겠습니다!

매개변수 n의 최대가 10이므로 모든 경우의 수를 구하면 184756개 정도이다.

 

모든 경우를 list에 담은 뒤 각 경우에 따라 라이언이 이겼는지 어피치가 이겼는지 계산한 다음

라이언과 어피치 점수 차가 가장 큰 경우를 찾아간다.

 

if apeach_score < rion_score:
    diff = rion_score - apeach_score
    if diff > score_diff:
        score_diff = diff
        answer = rion_case

 

처음엔 이렇게만 썼는데 테스트케이스 8번, 18번이 틀렸다.

"질문하기"를 찾아보니 입력값 3, [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1] / 출력값 [1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]인 경우를 해결하라고 되어 있어서 살펴보니

출처:

https://school.programmers.co.kr/questions/72101

프로그래머스

 

똑같이 점수 차가 나는 여러 가지 경우의 수가 존재했다.

그래서 문제를 다시 읽어보니

 

라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
예를 들어, [2,3,1,0,0,0,0,1,3,0,0]과 [2,1,0,2,0,0,0,2,3,0,0]를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]를 return 해야 합니다.
다른 예로, [0,0,2,3,4,1,0,0,0,0,0]과 [9,0,0,0,0,0,0,0,1,0,0]를 비교하면[9,0,0,0,0,0,0,0,1,0,0]를 return 해야 합니다.

 

이런 조건이 있었다!

이후 이 조건에 대한 처리도 추가해주니 정답 ㅎㅎ

 

💻 코드 & 설명

from itertools import combinations

def solution(n, info):
    answer = []
    cases = []
    
    for bars in combinations(range(n + 10), 10):
        case = []
        last = -1
        for bar in bars:
            case.append(bar - last - 1)
            last = bar
        case.append(n + 10 - last - 1)
        cases.append(case)
    
    score_diff = 0
    
    for rion_case in cases:
        apeach_score = 0
        rion_score = 0
        
        for i in range(11):
            if info[i] == 0 and rion_case[i] == 0:
                continue
            if info[i] < rion_case[i]:
                rion_score += (10 - i)
            else:
                apeach_score += (10 - i)
        
        if apeach_score < rion_score:
            diff = rion_score - apeach_score
            if diff > score_diff:
                score_diff = diff
                answer = rion_case
            elif diff == score_diff:
                for i in range(10, -1, -1):
                    if rion_case[i] > answer[i]:
                        answer = rion_case
                        break
                    elif rion_case[i] < answer[i]:
                        break
    
    return answer if answer else [-1]

 

 

✨ 회고 / 느낀 점

문제를 잘 읽자!

 

💭 나는 itertools 패키지를 사용해서 풀었는데 dfs(재귀)로 푼 경우가 깔끔하고 잘 푼 것 같았다.

코테에 따라 패키지 사용이 안될 수 있으니 조합을 직접 구현해보거나 패키지 없이 구현하는 것을 연습해야겠다