(Programmers/Python) 프로그래머스 (Lv.2) 양궁 대회 문제 해결

문제 설명

카카오 배 양궁 대회가 열렸습니다.


라이언은 지난번 카카오선 양궁 대회 우승자이며, 이번 대회에도 결승전까지 올라왔습니다.

결승전 상대는 아피치입니다.


카카오 선 양궁 대회 운영 위원회는 선수의 연속 우승이 아니라 다양한 선수들이 양궁 대회에서 우승하고 싶다고 생각합니다.

따라서 양궁 대회 운영위원회는 결승전의 규칙을 전 대회의 승자인 라이언에게 불리하게 다음과 같이 정했다.

1. 아피치가 화살 n 다리를 쏠 후 라이언은 화살 n 다리를 쏴.
2. 점수를 계산합니다.
   
   
   1. 저녁은 아래 사진처럼 보이며 최소 원의 목표점은 10점, 최대 원의 바깥쪽은 목표점이 0점입니다.
      
      
      

      
      

   2. 만약, k(k는 1~10 사이의 자연수) 점을 아피치가 a 다리를 맞추고, 라이언이 b 다리를 맞았을 경우, 보다 많은 화살을 k점에 맞춘 선수가 k점을 취합니다.
      
      그러나 a = b이면, 연설은 k 포인트를 취합니다.
      
      k점을 여러 발 맞추어도 k점보다 많은 점수를 취하는 것이 아니라 k점만 가져가는 것에 주의해 주세요. 또한 a = b = 0이면, 즉 라이언과 아피치가 모두 k 점에 하나의 화살표 만 닿으면 아무도 k 점을 취하지 않습니다.
      
      
      • 예를 들어, 아피치가 10점을 2발 맞추고, 라이언도 10점을 2발 맞았을 경우, 아피치는 10점을 취한다.
        
        
      • 또 다른 예로, 아피치가 10점을 0발, 라이언이 10점을 2발 치면, 라이언은 10점을 취합니다.
        
        
   3. 모든 코스 점수에 대해 각 선수의 최종 점수를 계산합니다.
      
      
3. 최종 득점이 높은 선수를 승자로 결정합니다.
   
   하지만 최종 점수가 같으면 연설을 승자에게 결정합니다.
   
   

현재 상황은 아피치가 화살 n 다리를 전부 쏘고 나서 라이언이 화살을 쏠 차례입니다.


라이언은 애피치를 최대 점수 차이로 이기기 위해 n다리의 화살을 어떤 목표점수에 맞추어야 하는지를 구하려고 합니다.

화살의 수를 포함한 자연수 n, 아피치가 맞은 이그널 스코어의 개수를 10점부터 0점까지 순서대로 넣은 정수 배열 info가 매개변수로 주어집니다.

이때 라이언이 최대 점수 차이로 우승하기 위해 n 다리의 화살을 어떤 목표 점수에 맞추어야 하는지를 10점부터 0점까지 순서대로 정수 배열에 넣어서 return하도록 솔루션 함수를 완성합니다.

만약 라이언이 우승할 수 없는 경우(무조건이 되거나 날 경우)는 (-1)을 반환합니다.

---

제한사항

• 1≤ n ≤10
• 정보 길이 = 11
  • 0 ≤ info의 요소≤ n
  • 정보의 원소 합계 = n
  • info의 i번째 요소는 10 – i 점을 맞춘 화살의 수입니다.
    
    (i는 0~10의 정수입니다.
    
    )
• 라이언이 이기는 방법이 있는 경우, return 하는 정수 배열의 길이는 11 입니다.
  
  
  • 0 ≤ return 할 정수 배열의 요소 ≤ n
  • return 할 정수 배열의 요소 합계 = n (반드시 n 다리를 모두 쏠 필요가 있습니다.
    
    )
  • return 할 정수 배열의 i 번째 요소는 10 – i 점을 맞춘 화살의 수입니다.
    
    (i는 0~10의 정수입니다.
    
    )
  • 라이언이 가장 큰 점수 차이로 승리할 수 있는 몇 가지 방법이 있다면 가장 낮은 점수를 더 맞추는 경우를 반환합니다.
    
    
    • 최저 점수를 합한 개수가 같으면 계속해서 낮은 점수를 더 합한 경우를 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 해야 합니다.
      
      
• 라이언이 이길 방법이 없는 경우, return 하는 정수 배열의 길이는 1 입니다.
  
  
  • 라이언이 어떻게 화살을 쏘는가? 라이언의 스코어가 아피치의 스코어 이하이면 (-1) 을 return 해야 합니다.
    
    

---

입출력 예

ninforesult

---

입출력 예 설명

입출력 예 #1

아피치와 라이언이 다음과 같이 화살을 맞으면,

골 스코어 피치가 맞는 화살의 개수 라이언이 맞은 화살의 개수 결과

아피치의 최종 득점은 15점, 라이언의 최종 득점은 19점입니다.

4점 차이로 라이언이 우승합니다.

그러나 라이언이 다음과 같이 화살을 치면 더 큰 스코어카에서 우승할 수 있습니다.

골 스코어 피치가 맞는 화살의 개수 라이언이 맞은 화살의 개수 결과

아피치의 최종 득점은 17점, 라이언의 최종 득점은 23점입니다.

6점 차이로 라이언이 우승합니다.

그러므로 (0,2,2,0,1,0,0,0,0,0,0) 을 return 해야 합니다.

입출력 예 #2

라이언이 10점을 맞아도 아피치가 10점을 취하게 됩니다.


그러므로 라이언은 우승할 수 없기 때문에 (-1) 을 return 해야 합니다.

입출력 예 #3

아피치와 라이언이 다음과 같이 화살을 맞으면,

골 스코어 피치가 맞는 화살의 개수 라이언이 맞은 화살의 개수 결과

아피치의 최종 득점은 10점, 라이언의 최종 득점은 39점입니다.

29점 차이로 라이언이 우승합니다.

그러나 라이언이 다음과 같이 화살을 치면

골 스코어 피치가 맞는 화살의 개수 라이언이 맞은 화살의 개수 결과

아피치의 최종 득점은 13점, 라이언의 최종 득점은 42점입니다.

이 경우도 29점 차이로 라이언이 우승합니다.


하지만 첫 번째 사례와 두 번째 사례를 비교했을 때 두 번째 사례가 두 사례 중 가장 낮은 점수인 네 점이 더 일치했기 때문에 (1,1,2,3,0,2,0,0,0,0,0)이 아님 (1,1,2,0,1,2,2,0,0,0,0) 을 return 해야 합니다.

입출력 예 #4

최대 점수 차이로 이길 경우 중 가장 낮은 점수를 가장 많이 합한 10~3점을 1발씩 맞추고 나머지 2족을 0점에 맞추는 경우이다 (1,1,1,1,1,1,1,1,0,0,2) 를 return 해야 합니다.

---

사고의 흐름

1. n의 길이와 info 배열의 크기가 크지 않기 때문에, 모든 케이스의 수를 모두 탐색하는 완전 탐색 알고리즘을 생각한다

2. 처음에는 규칙성을 찾아서 문제를 해결했지만 오해가 많이 있었고 다른 방법을 생각했습니다.

3. 중복 조합 사용의 힌트를 얻어 문제를 풀었다

3-1. 중복 조합으로 lion이 n번의 화살을 쏘는 모든 경우의 수를 만들었다

3-2. 각 케이스의 수를 돌리면서 lion의 스코어리스트를 작성해, info에 비해 apeach와 lion의 스코어 차이를 구했다.

문제의 핵심과 알고리즘

가능한 모든 사례의 수를 완전히 탐색하는 문제

(나는 중복 조합으로 모든 사례의 수를 탐색하고 dfs를 통해서도 가능)

from itertools import combinations_with_replacement

def solution(n, info):
    answer = (-1)
    maxval= 0
    combi = list(combinations_with_replacement(range(0, 11), n))

    for c in combi:
        lion_list = (0 for i in range(len(info)))
        apeach, lion = 0, 0

        for i in c:
            lion_list(10 - i) += 1

        for i in range(11) :
            if info(i)!
=0 and info(i)==lion_list(i) :
                apeach+=10-i
            elif info(i)>lion_list(i) :
                apeach+=10-i
            elif info(i)<lion_list(i) :
                lion+=10-i

        if lion-apeach>maxval :
            answer=lion_list
            maxval=lion-apeach

    print(answer)
    return answer

문제를 해결하면서 잃어버린 부분

1. 중복 조합

처음에는 중복 조합과 같은 수학적 계산이 필요 없다고 단정하여 풀었다.

시간이 걸리고 중복 조합을 사용했다는 힌트를 받아 중복 조합을 통해 쉽게 풀었다.

=> from itertools import combinations_with_replacement에서 중복 조합 사용!

다른 풀이 참고로 배운 것

def solution(n, info):
    global answer, result

    def score(ryan):
        s = 0
        for i in range(11):
            if ryan(i) == info(i) == 0:
                continue
            if ryan(i) > info(i):
                s += 10 - i
            else:
                s -= 10 - i
        return s

    def dfs(idx, left, ryan):
        global answer, result
        if idx == -1 and left:
            return
        if left == 0:
            s = score(ryan)
            if result < s:
                answer = ryan(:)
                result = s
            return
        for i in range(left, -1, -1):
            ryan(idx) = i
            dfs(idx-1, left-i, ryan)
            ryan(idx) = 0

    answer = (0 for _ in range(11))
    result = 0
    dfs(10, n, (0 for _ in range(11)))
    return answer if result !
= 0 else (-1)

이 해결책은 dfs를 활용한 문제다.

내일 dfs를 활용해 꼭 다시 풀어봐야 한다.

총평

문제를 읽고 입력 데이터 크기를보고 전체 탐색 문제임을 알고 dfs를 먼저 기억했습니다.

그러나 dfs를 쓰는 것을 싫어한다.

연습이 서둘러 필요) 다른 방법을 생각하는 조금 잘못된 방향으로 간 것 같습니다.

꼭 완전하게 탐색하는 방법에 dfs나 bfs만이 있다고는 생각하지 않고, 구글을 적극적으로 활용해 적절한 모듈을 찾아 빨리 해방하자.