프로그래머스 연습문제 - 카운트다운

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/131129

접근

dp배열을 선언하고 각각의 인덱스에 해당 인덱스 만큼의 점수를 얻을 수 있는 다트의 최소 갯수와, 해당 다트의 갯수일때 싱글or 불의 다트의 갯수가 최대가 되는 이차원 배열을 넣어주고 dp[target]의 값을 반환해주면 정답임.

일단 얻을 수 있는 점수들을 원소로 하는 배열point_list를 선언하고, dp 배열의 인덱스가 point_list에 포함되어 있으면 해당 인덱스의 값을 [1,0]을 넣어줌 (싱글이나 불일때는 [1,1]로 넣어준다). 그리고 포함되어 있지 않으면 0을 넣어준다

그 후 dp배열을 순회하면서, 해당 인덱스가 참조하는 값이 0인 경우, 해당 인덱스에서 point_list의 값들을 하나씩 뺀 값이 참조하는 값들을 확인하면서, dp배열을 문제 조건에 맞게 갱신해주면 정답임.

전체 코드

def solution(target):
    target_list=[0 for i in range(target+1)]
    # target점수를 딱! 맞춰야함
    # single 이나 bull 갯수가 적어여돼
    num_of_single_bull=0
    point_list=[]
    single=[i for i in range(1,21)]
    single.append(50)
    double=[i*2 for i in range(11,21)]
    tripple=[21,27,33,39,42,45,48,51,54,57,60]
    point_list=single+double+tripple
    point_list.sort()
    point_list=set(point_list)
    target_list=[0 for i in range(target+1)]
    for i in point_list:
        if i<=target:
            if i in single:
                target_list[i]=[1,1]
            else:
                target_list[i]=[1,0]
    
    for i in range(1,target+1):
        if target_list[i]==0:
            for j in point_list:
                if i>j:
                    if j in single:
                        if target_list[i]==0:
                            target_list[i]=[1+target_list[i-j][0],1+target_list[i-j][1]]
                        else:
                            if target_list[i][0]>target_list[i-j][0]+1:
                                target_list[i]=[target_list[i-j][0]+1,target_list[i-j][1]+1]
                            elif target_list[i][0]==target_list[i-j][0]+1 and target_list[i-j][1]+1>target_list[i][1]:
                                target_list[i]=[target_list[i-j][0]+1,target_list[i-j][1]+1]
                    else:
                        if target_list[i]==0:
                            target_list[i]=[1+target_list[i-j][0],target_list[i-j][1]]
                        else:
                            if target_list[i][0]>target_list[i-j][0]+1:
                                target_list[i]=[target_list[i-j][0]+1,target_list[i-j][1]]
                            elif target_list[i][0]==target_list[i-j][0]+1 and target_list[i-j][1]>target_list[i][1]:
                                target_list[i]=[target_list[i-j][0]+1,target_list[i-j][1]]
    answer = target_list[-1]
    return answer

참고

x