글 읽기 - 시간초과 오류가 나오는데 한번 봐주시겠어요 ㅠㅠ

l7839n 8년 전 0

답은 정확하게 나오는 것 같은데 시간초과 오류가 나옵니다.

아무래도 k값을 만들기 위해서 동전의 가치를 위에서 부터 아래로 탐색할 때 각 동전의 가치마다 n번씩 확인하게 되므로

결과적으로 최악의 경우 O(n^k)의 시간복잡도가 나와서 그런 것 같은데 해결방법을 강구해보려고 해도 잘 떠오르지를 않네요 ㅠㅠ

도움 좀 부탁드립니다

#file = open("test_case.txt")

test_case = input()
#test_case = file.readline()

test_num_arr = test_case.split(" ")

n = int(test_num_arr[0])
k = int(test_num_arr[1])

result_list = [99999] * (k+1)
case_arr = []
coin_num = 1

for i in range(n):
    case = int(input())
    #case = int(file.readline())
    if case == k:
        print(1)
        exit()
    if case > k:
        continue
    case_arr.append(case)
    result_list[case_arr[-1]] = coin_num

def find_opt(won):
    if won <= 0:
        return 99999

    elif result_list[won] != 99999:
        return result_list[won]

    for case_value in case_arr:
        if won <= case_value:
            continue

        temp_won = find_opt(won-case_value)
        if temp_won == 99999:
            pass
        elif temp_won+1 < result_list[won]:
            result_list[won] = temp_won+1

    return result_list[won]

result = find_opt(k)
if result is 99999:
    print(-1)
else:
    print(result)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 오류가 나오는데 한번 봐주시겠어요 ㅠㅠ

l7839n 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말