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

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

코딩테스트 연습 - 양궁대회

 

 

풀이

다른 사람의 풀이 보니까 DFS로 풀었던데 난 비트를 이용해서 풀었다.

총 점수는 점수*화살 수가아니라 한 점수구간에 1발이상 맞히면 그 점수이다. + 총점이 아니라 점수차가 크도록 해야한다.

이 부분때문에 헤맸다..

 

1에서부터 1111111111(11자리. 2047)까지 돌리는데, 1이 해당하는 점수는 최소 1발이상 맞힌 것으로해서 점수 차를 구한다.

 

최소 1발씩 쏴야하므로 1의 갯수가 n보다 적은 경우만 고려한다.

어피치가 못 쏜 점수는 1발을, 쏜 점수는 어피치보다 1발 더 추가하는데 이렇게 추가해서 화살이 모자라면 -1을 리턴한다.

이렇게 추가하고 화살이 남으면 맨 마지막 1인 위치에 나머지 화살을 더한다.

점수차와 최댓값을 비교해서 최댓값인 경우 answer리스트에 담아뒀다가 맨 마지막에 작은 점수를 많이 쏜 게 무엇인지 찾는다.

def sol(bit, n, info):
    arrow = n
    score = 0
    apeach = 0
    tmp = [0,0,0,0,0,0,0,0,0,0,0]
    for i in range(len(info)):
        if info[i] > 0:
            apeach += (10-i)
    #마지막 '1'의 인덱스 찾기
    last_b = len(bit) - bit[::-1].index('1') -1
    
    for i in range(0, 10):
        if bit[i] == '1':
            if info[i] != 0:
                apeach -= (10-i)
            arrow -= info[i]+1
            tmp[i] = info[i]+1
            score += 10-i
        #화살 모자라면 return -1
        if arrow < 0:
            return tmp, -1
    #화살 남으면 맨 마지막 '1' 인덱스에 추가하기
    if arrow > 0:
        tmp[last_b] += arrow
    diff = score - apeach
    
    return tmp, diff


def solution(n, info):
    answer = []
    maxi = 0
    
    #b = 1~2047
    b = 1
    while b < 2048:
        #binary로 바꾸고 11자리 0으로 채우기
        bit = bin(b)[2:13].zfill(11)
        cnt = 0
        cnt = bit.count('1')

        if cnt <= n:
            tmp, diff = sol(bit, n, info)
            # 둘의 점수 차가 커지면 answer 갱신, 추가
            if diff > maxi and tmp != info:
                maxi = diff
                answer = []
                answer.append(tmp)
            elif diff == maxi and tmp != info:
                answer.append(tmp)
        b += 1
    
    #같은 점수 차일 경우 제일 낮은 점수 화살 수 가 많은 사람이 승리
    ans = []
    if len(answer) == 0 or maxi == 0:
        return [-1]
    elif len(answer) == 1:
        return answer[0]
    elif len(answer) > 1:
        for i in range(10, 0, -1):
            max_val = 0
            for a in answer:
                if a[i] >= max_val:
                    ans = a
                    max_val = a[i]
            if max_val != 0:
                break
    return ans