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

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

🔗 문제 링크

---

문제 설명 📄

어피치와 라이언이 n발의 화살로 점수를 겨루는 게임. 어피치는 이미 화살을 쏜 상태이고, 라이언은 남은 n발을 적절히 배분하여 가장 큰 점수 차이로 승리해야 한다. 만약 동일한 점수 차이가 나면 낮은 점수를 더 많이 맞힌 경우를 선택한다.

---

문제 접근 방식 💡

• DFS(깊이 우선 탐색) 백트래킹을 활용하여 모든 가능한 라이언의 화살 배치를 탐색.
• 라이언이 어피치보다 +1개 더 맞추거나, 해당 점수를 포기하는 두 가지 선택이 가능.
• 점수 차이를 계산하여 best_diff를 갱신하고, 가장 큰 점수 차이를 가진 경우를 선택.
• best_diff가 0 이하라면 라이언이 승리할 방법이 없으므로 [-1]을 반환.
• 여러 경우가 있을 경우 가장 낮은 점수를 많이 맞힌 경우를 선택.

---

Solution 💻

import sys
sys.setrecursionlimit(10**7)

def solution(n, info):
    global best_diff, candidates
    best_diff = 0  
    candidates = []  
    
    def dfs(remain, lion_arrows, index):
        global best_diff, candidates
        if index == -1:
            lion_arrows[10] += remain  
            
            lion_score = 0
            apeach_score = 0
            
            for i in range(11):
                if lion_arrows[i] == 0 and info[i] == 0:
                    continue
                if lion_arrows[i] > info[i]:
                    lion_score += (10 - i)
                else:
                    apeach_score += (10 - i)
            diff = lion_score - apeach_score
            
            if diff > best_diff:
                best_diff = diff
                candidates = [lion_arrows[:]]
            elif diff == best_diff:
                candidates.append(lion_arrows[:])
                
            lion_arrows[10] -= remain  
            return
        
        dfs(remain, lion_arrows[:], index-1)
        
        arrows_needed = info[index] + 1
        if arrows_needed <= remain:
            new_arrows = lion_arrows[:]
            new_arrows[index] = arrows_needed
            dfs(remain - arrows_needed, new_arrows, index-1)
    
    dfs(n, [0]*11, 10)
    
    if best_diff <= 0:
        return [-1]
    
    candidates.sort(key=lambda arr: arr[::-1], reverse=True)
    return candidates[0]

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(2^11)
  • 11개의 점수에서 각각 선택(맞추거나 안 맞추거나)해야 하므로 최악의 경우 2^11 = 2048번의 재귀 호출 발생.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(2^11 * 11)
  • candidates 리스트에 최적의 결과를 저장하므로 최대 O(2048 * 11) ≈ O(10^4) 정도의 메모리 사용.

---

리팩토링 🛠️

from itertools import combinations

def solution(n, info):
    best_diff = 0
    best_shot = [-1]

    for comb in combinations(range(11), n):  
        lion_arrows = [0] * 11
        for i in comb:
            lion_arrows[i] = info[i] + 1  

        remain = n - sum(lion_arrows)
        if remain < 0:
            continue
        lion_arrows[10] += remain  

        lion_score = sum((10 - i) for i in range(11) if lion_arrows[i] > info[i])
        apeach_score = sum((10 - i) for i in range(11) if lion_arrows[i] <= info[i] and info[i] > 0)
        diff = lion_score - apeach_score

        if diff > best_diff:
            best_diff = diff
            best_shot = lion_arrows[:]
        elif diff == best_diff:
            if lion_arrows[::-1] > best_shot[::-1]:
                best_shot = lion_arrows[:]

    return best_shot if best_diff > 0 else [-1]

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(2^11) (비슷)
  • 하지만 itertools.combinations()를 활용하여 가독성을 향상.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(11)
  • 최적의 배열 best_shot만 저장.