PGS 131129 카운트 다운 (PGS, Lv3, python)

문제 해석 및 접근

문제가 꽤나 복잡하게 설명하고 있지만, 결과적으로 최대한 적은 횟수로 해당 점수를 만들어 내는 문제입니다. 그 과정에서 같은 횟수인 경우 싱글이나 불이 많은 방법을 찾아야합니다.

target은 최대 100,000이고 선택할 수 있는 숫자가 1~20 그리고 각 값에 2 , 3, 50까지 많은 선택지가 있습니다.
그래서 처음에는 경우의 수를 탐색하기보다 target을 60으로 나누어서 가장 적은 횟수를 구하기 위해 조건으로 나눠가며 한 번에 정답을 구하는 방법을 찾으려 했습니다.
( 하지만 적은 케이스만 정답을 구하는 방법 이었고.. 다시 문제를 풀어야하는 상황! )

모든 케이스를 확인해야 된다고 생각하여 제가 자주 사용하는 방법인 검토해야하는 값을 배열로 담는 방법을 떠올렸고 이 문제를 DP 방식으로 해결했습니다.

"""
1 ~ 20 / *2 *3
22 24 26 28 ~~~ 40
21 24 27 30 33 36 39 42 45 48 51 54 57 60 
50

150 => 50 3 / 60 60 30 

"""
def solution(target):
    dtSet = set()
    greatList = list(range(1, 21))
    greatList.append(50)
    for i in range(1, 21):
        if i*2 > 20:
            dtSet.add(i*2)
        if i*3 > 20:
            dtSet.add(i*3)
            
    result  = list([999999999, 999999999] for _ in range(100061))
    result[0] = [0, 0]
    for i in range(0, 100000):
        for num in greatList:
            if result[num+i][0] > result[i][0] + 1:
                result[num+i] = [result[i][0]+1, result[i][1]+1]
            elif result[num+i][0] == result[i][0]+1 and result[num+i][1] < result[i][1] + 1:
                result[num+i][1] = result[i][1] + 1
        for mul in dtSet:
            if result[mul+i][0] > result[i][0] + 1:
                result[mul+i] = [result[i][0]+1, result[i][1]]
            elif result[mul+i][0] == result[i][0]+1 and result[mul+i][1] < result[i][1]:
                result[mul+i][1] = result[i][1]
    
    answer = result[target]
    return answer

해결 및 주의사항, 팁

위의 코드에서는 1에서 100,000까지의 모든 값을 하나의 배열을 구해 어떤 테스트에도 활용 할 수 있다는 아이디어로 배열 범위를 저렇게 설정했지만, 실제로는 target에 해당하는 값으로 설정한다면 개별테스트에 대해 훨씬 속도가 빠를 것입니다.
또한 저는 현재의 값을 기준으로 다음 값들을 채우는 식으로 했는데, 현재의 값을 과거 값을 기준으로 채우는 방식으로 알고리즘을 작성한다면 시간 복잡도를 조금 더 줄일 수 있을 것 같네요.
( 100,061로 해버린 것은 밑에서 조건문을 길게 쓰기 싫어서 입니다 ... ㅎㅎ )