[2022 KAKAO BLIND RECRUITMENT] 양궁대회

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

프로그래머스

 

잘못된 접근

DP로 접근했는데 애초에 재귀를 보면서 분명 같은 경우를 살펴볼 일이 없어야 하는데... 같은 경우를 체크한다...ㅠㅠㅠ 

실패한 소스코드

import copy

frodo = [0 for _ in range(11)]
answer = []
max_gap = 0

def cmpScore(frodo, apeach):
    score_f = 0
    score_ap = 0
    for i in range(11):
        if frodo[i] > apeach[i]:
            score_f += 10-i
        elif frodo[i] <= apeach[i] and apeach[i] != 0:
            score_ap += 10-i
        else:
            continue
    return score_f - score_ap

def isFrodoWinner(frodo, apeach):
    score_f = 0
    score_ap = 0
    for i in range(11):
        if frodo[i] > apeach[i]:
            score_f += 10-i
        elif frodo[i] <= apeach[i] and apeach[i] != 0:
            score_ap += 10-i
        # k점에 아무도 못 맞힌 경우
        else:
            continue
    if score_f > score_ap:
        return True
    else:
        return False
    
def shoot(score, n, info):
    global max_gap
    # 해당 점수 맞히는 경우
    frodo[10-score] = info[10-score] + 1
    if sum(frodo) == n:
        # print(frodo, isFrodoWinner(frodo, info))
        if isFrodoWinner(frodo, info):
            if len(answer) == 0:
                answer.append(copy.deepcopy(frodo))
                max_gap = cmpScore(frodo, info)
            else:
                if max_gap < cmpScore(frodo, info):
                    answer.clear()
                    answer.append(copy.deepcopy(frodo))
                    max_gap = cmpScore(frodo, info)
                elif max_gap == cmpScore(frodo, info):
                    answer.append(copy.deepcopy(frodo))
            return
    
    elif sum(frodo) > n:
        frodo[10-score] = 0
        if score - 1 < 0:
            return
        else:
            shoot(score-1, n, info)
    else:
        if score - 1 < 0:
            return
        else:
            shoot(score-1, n, info)
    
    # 해당 점수 안맞히고 넘어가는 경우
    frodo[10-score] = 0
    if score - 1 < 0:
        return
    else:
        shoot(score-1, n, info)

def solution(n, info):
    shoot(10, n, info)
    
    if len(answer) == 0:
        answer.append([-1])
    else:
        answer.sort(key=lambda x:(-x[10], -x[9], -x[8], -x[7], -x[6], -x[5], -x[4], -x[3], -x[2], -x[1], -x[0]))            
    print(answer)
    return answer[0]

 

---

올바른 접근

완전 탐색으로 접근

0점부터 10점까지 모든 점수를 획득할지 말지만 결정하면 되므로 모든 경우의 수는 2^11 로 충분히 살펴볼 수 있다. 2시간 넘게 DP로 끙끙 앓았더니 슬프다. 운동하고 와서 다른 사람 코드 좀 보고... 카카오 코테 보기 전날 한번 더 완탐 문제들 풀어볼 때 다시 봐야겠다. 아직 문제 유형을 파악하는데 서툴구만 흑

 

BFS 접근

1. 10점부터 0점까지 화살 쏨

현재 몇점인지 : score ( 0 -> 10점과녁)

현재 라이언 과녁 상황 : lion [0 for _ in range(11)]

 

2. 어피치를 이기려면

 1) 어피치보다 +1발

 2) 해당 점수 포기

* 주의할 점은 그냥 '=' 연산자 써서는 X. copy() 메소드로 깊은 복사 해주자.

( 2차원 이상의 배열을 깊은 복사 해주려면 copy 라이브러리의 deepcopy() 메소드 써야한다. 리스트의 copy() 메소드는 1차원까지만 깊은 복사 지원 )

 

3. 조건 체크

 1) 화살을 n발보다 더 쏜 경우 ( sum(lion) > n ) : 패스

 2) 0점까지 갔는데 다 못 쏜 경우 ( score == 10 ): 마지막 과녁에 다 쏘기

 3) 다 쏜 경우 ( sum(lion) == n ) : 점수 계산. 최대 점수차 갱신해가면서 최대 점수차를 내는 경우만 따로 배열로 저장하기

 

4. shoot() 함수를 실행한뒤 최종 조건 체크

 1) 리턴값이 빈 배열인 경우 : [-1] 리턴

 2) 리턴값 배열의 길이가 1인 경우 : 해당 배열 리턴

 3) 그 외의 경우 : 가장 낮은 점수를 많이 맞힌 경우 리턴.

  * score을 통해 가장 높은 점수부터 쏘기 시작했으므로 배열의 가장 마지막 요소가 해당됨.

 

python 코드

from collections import deque


def shoot(n, info):
    q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])
    result = []  # 가능한 시나리오 모두 저장
    max_gap = 0  # 최대 점수차

    while q:
        score, lion = q.popleft()

        # 화살 다 쐈으니 점수 계산
        if sum(lion) == n:
            score_ap, score_l = 0, 0
            for i in range(11):
                if not (info[i] == 0 and lion[i] == 0):
                    if info[i] >= lion[i]:
                        score_ap += 10 - i
                    else:
                        score_l += 10 - i

            if score_ap < score_l:
                gap = score_l - score_ap
                if max_gap > gap:
                    continue
                if max_gap < gap:
                    max_gap = gap
                    result.clear()
                result.append(lion)
        # 화살을 n발보다 더 쏜 경우
        elif sum(lion) > n:
            continue

        # 마지막 과녁까지 간 경우, 화살 마지막 과녁에 다 쏘기
        elif score == 10:
            tmp = lion.copy()
            tmp[score] = n - sum(tmp)
            q.append((-1, tmp))

        # 슛슛슛
        else:
            # 어피치보다 1발 더
            shoot_lion = lion.copy()
            shoot_lion[score] = info[score] + 1
            q.append((score + 1, shoot_lion))
            # 해당 점수 포기, 패스
            giveup_lion = lion.copy()
            giveup_lion[score] = 0
            q.append((score + 1, giveup_lion))

    return result


def solution(n, info):
    answer = []

    all_cases = shoot(n, info)

    if len(all_cases) == 0:
        answer.append(-1)
    elif len(all_cases) == 1:
        answer = all_cases[0]
    else:
        answer = all_cases[-1]
    return answer

 

 

언제쯤 익숙해지냐 완전탐색.. BFS... DFS...  끙