프로그래머스 양궁대회

문제 링크

1. 상대방과의 점수차가 가장 큰 경우의 수를 찾되
2. 같은 점수일 경우 가장 낮은 과녁에 쏜 경우를 return해야 하는 최적화 문제.

쏠 수 있는 화살의 갯수인 n의 크기가 10이하, 화살을 쏠 수 있는 위치도 11가지로 제한되어 있어 수월해야 할 문제이다. 근데 생각보다 어려워서 쉽지 않았다.

포인트
1. 상대방이 이미 화살을 쏜 곳에 화살을 쏘는 경우 상대방의 점수가 감소 + 내 점수가 증가하므로 2배의 효용을 얻을 수 있다.
2. 어디에 화살을 쏘더라도 이득이 없는 경우 화살은 0점에 몰아서 쏴야 한다.

1. 기댓값

def solution(n, info):
    answer = [0]*11
    # 정답을 담을 리스트
    weight = [0]*11
    # 각 과녁에 화살을 쏠 경우 한 화살 당 기댓값을 담을 리스트
    # 화살 한방 당 기댓값 + 점수 기록
    for i in range(11):
        if info[i]:
            weight[i] = ((10-i) * 2 / (info[i]+1), 10-i)
            # 상대방의 점수를 뺏어오는 것 + 내 점수에 더해지는 것
            # => 2배의 점수를 얻는 데 필요한 화살발수만큼으로 나눔
        else:
            weight[i] = ((10-i), 10-i)
            # 내 점수에 더해지는 것만 1발을 쏴서 얻을 수 있다.
    weight.sort(key = lambda x: (-x[0],-x[1]))
    # 화살 한 방당 기댓값이 높은 애들 먼저 + 높은 점수 먼저
    for dump, index in weight:
        if n > info[10-index]:
            answer[10-index] = info[10-index] +1
            n -= info[10-index]+1
    answer[10] = n
    # 남는 화살은 0점 과녁에 몰기
    a_score = 0
    r_score = 0
    # 어피치와 라이언의 점수 계산하기
    for i in range(10):
        if answer[i] or info[i]:
            if answer[i] > info[i]:
                r_score += (10-i)
            else:
                a_score += (10-i)
    if a_score >= r_score:
        return [-1]
    else: return answer

그런데 solution(2, [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0])의 경우 9점에다 2발을 쏴서 1점 차로 이기는 경우가 최적임에도 불구하고 한 발의 기댓값이 10점에 쏘는 경우가 제일 높고, 그 다음에 9, 8점에 쏘는 기댓값이 높으나 불가능하여 7점에 한 발을 쏘게 되어 동점으로 결과가 남는 경우가 등장했다. 어떤 방식으로 개선을 해야 할 지 모르겠어서 다른 방식을 채택했다.

2. DFS

def solution(n, info):
    # 최종 결과로 반환할 최대 점수 차이와 가장 좋은 화살 배분 결과를 저장
    max_diff = 0
    best_result = [-1]

    # 라이언과 어피치의 점수를 계산하는 함수
    def calculate_score(ryan):
        apeach_score, ryan_score = 0, 0
        for i in range(11):  # 0점 ~ 10점까지 반복
            # 어피치와 라이언 둘 다 해당 점수에 화살을 쏘지 않은 경우
            if info[i] == 0 and ryan[i] == 0:
                continue
            # 어피치가 같은 점수에서 화살을 더 많이 쏜 경우
            if info[i] >= ryan[i]:
                apeach_score += 10 - i  # 어피치 점수에 추가
            else:
                ryan_score += 10 - i  # 라이언 점수에 추가
        # 라이언 점수가 어피치 점수보다 높을 때만 점수 차이를 반환
        return ryan_score - apeach_score if ryan_score > apeach_score else 0

    # 백트래킹 함수: 화살을 배분하는 모든 경우의 수를 탐색
    def backtrack(idx, arrows_left, ryan):
        nonlocal max_diff, best_result  # 함수 외부 변수에 접근하기 위해 nonlocal 사용

        # 종료 조건: 모든 점수를 확인했거나 화살을 모두 사용했을 때
        if idx == 11 or arrows_left == 0:
            ryan[10] += arrows_left  # 남은 화살을 0점에 모두 배치
            diff = calculate_score(ryan)  # 점수 차이 계산
            # 점수 차이가 최대값이거나 같은 점수 차이일 때 더 낮은 점수를 많이 맞힌 경우 갱신
            if diff > max_diff or (diff == max_diff and ryan[::-1] > best_result[::-1]):
                max_diff = diff  # 최대 점수 차이 갱신
                best_result = ryan[:]  # 현재 화살 배분 상태 저장
            ryan[10] -= arrows_left  # 원래 상태로 복구
            return

        # 1. 라이언이 현재 점수에서 이기기 위해 화살을 쏘는 경우
        if arrows_left > info[idx]:  # 남은 화살이 어피치보다 더 많이 쏠 수 있을 때
            ryan[idx] = info[idx] + 1  # 어피치보다 1발 더 쏨
            backtrack(idx + 1, arrows_left - ryan[idx], ryan)  # 다음 점수로 이동
            ryan[idx] = 0  # 원래 상태로 되돌림

        # 2. 현재 점수에 화살을 쏘지 않는 경우
        backtrack(idx + 1, arrows_left, ryan)

    # 백트래킹 함수 호출: 0번 점수부터 시작하고 n발의 화살을 배분
    backtrack(0, n, [0] * 11)

    # 결과 반환: 점수 차이가 0보다 크면 최적의 화살 배분, 그렇지 않으면 [-1]
    return best_result if max_diff > 0 else [-1]

그래서 모든 과녁에 화살을 쏘는 방식으로 완전탐색을 했다. 그랬더니 통과는 했지만... 만약에 과녁이 11개만 있는게 아니라 더 다양하게 있었다면? n이 늘어난다 하면 이대로 괜찮을까? 싶어서 다른 방식으로도 풀어봤다.

3. DP

def solution(n, info):
    # 상대방(어피치)의 초기 점수 총합을 계산
    # info[i]가 1 이상이면 어피치가 해당 점수(10-i)를 획득한 것이므로 이를 더함
    counterpart_score = sum((10 - i) for i in range(10) if info[i])

    # DP 테이블 초기화: 
    # dp[j]는 j개의 화살을 사용했을 때의 [총 점수, 점수를 얻은 칸 위치 리스트]
    dp = [[0, []] for _ in range(n + 1)]

    # 각 점수 칸(10점부터 0점까지)을 탐색
    for i in range(10):
        c = info[i]  # 어피치가 해당 칸에 쏜 화살의 개수
        
        if c != 0:  
            # 상대방이 해당 점수 칸에서 이미 점수를 획득한 경우
            # 내가 점수를 얻으려면 상대방보다 1발 더 많이 쏴야 한다 (c + 1발 필요)
            for j in range(n - c - 1, -1, -1):  # 남은 화살 수를 거꾸로 탐색
                # j개의 화살을 사용한 상태에서 점수를 획득할 수 있는 조건
                # 조건 1: 이전 점수가 존재해야 함 (j == 0이거나 dp[j][0]이 존재)
                # 조건 2: 현재 점수를 더했을 때 최댓값을 갱신하는 경우
                if (j == 0 or dp[j][0]) and dp[j][0] + 2 * (10 - i) >= dp[j + c + 1][0]:
                    # 화살을 쏴서 점수 갱신
                    dp[j + c + 1][0] = dp[j][0] + 2 * (10 - i)
                    # 점수를 얻은 위치 리스트를 업데이트 (복사 후 append)
                    dp[j + c + 1][1] = dp[j][1].copy()
                    dp[j + c + 1][1].append(10 - i)
        else:
            # 상대방이 해당 점수 칸에 화살을 하나도 쏘지 않은 경우
            # 내가 화살을 1발만 쏴도 점수를 획득할 수 있음
            for j in range(n - 1, -1, -1):  # 남은 화살 수를 거꾸로 탐색
                # 조건 1: 이전 점수가 존재해야 함
                # 조건 2: 현재 점수를 더했을 때 최댓값을 갱신하는 경우
                if (j == 0 or dp[j][0]) and dp[j][0] + (10 - i) >= dp[j + 1][0]:
                    # 점수 갱신: 이전 점수에 (10 - i) 점수를 추가
                    dp[j + 1][0] = dp[j][0] + (10 - i)
                    # 점수를 얻은 위치 리스트를 업데이트
                    dp[j + 1][1] = dp[j][1].copy()
                    dp[j + 1][1].append(10 - i)

    # DP 테이블에서 최대 점수를 가지는 결과를 찾음
    max_comb = max(dp, key=lambda x: x[0])

    # 어피치의 점수를 넘지 못하면 라이언이 이길 수 없으므로 [-1] 반환
    if max_comb[0] <= counterpart_score:
        return [-1]

    # 결과 배열: 0점부터 10점까지 각 점수 칸에 라이언이 쏜 화살 개수를 저장
    ans = [0] * 11

    # max_comb[1]에 기록된 점수를 바탕으로 화살 개수를 할당
    for num in max_comb[1]:
        ans[10 - num] = info[10 - num] + 1  # 어피치보다 1발 더 많이 쏨

    # 남은 화살이 있으면 0점 칸에 모두 할당
    ans[10] = max(0, n - sum(ans))

    return ans

DP로 j개의 화살을 쐈을 때의 최댓값을 갱신해나가면서 최적해를 찾아낸다. 처음에 DP의 값을 앞에서부터 갱신했더니 최적해로 저장될 가능성이 있는 값들이 덮어 씌워지는 문제가 있어 뒤에서부터 앞으로 값을 갱신해나갔다.