글 읽기 - 어느 부분에서 시간을 더 줄여야 코드가 패스가 될까요?

atlanboa 4년 전 0

몇일 고민해봐도 제 능력에서는 잘 모르겠습니다. 알려주세요 ㅠㅠ

def search(target):
    
    if dp[target]:
        return dp[target]

    max_cost = 0

    for i in range(1, n+1):
        if rules[i][target]:
            max_cost = max(max_cost, search(i))
    dp[target] = max_cost + cost[target-1]
    return dp[target]



for _ in range(int(input())):
    n, k = map(int, input().split())
    cost = []
    dp = [0]*1001
    cost = list(map(int, input().split()))
    rules = [ [0]*(n+1) for _ in range(n+1)]
    for _ in range(k):
        x, y = map(int, input().split())
        rules[x][y] = 1
    target = int(input())
    print(search(target))

sait2000 4년 전 1

건물을 짓는 데 걸리는 시간이 0일수도 있는데, 만약에 모든 건물이 시간이 0이면 어떤 일이 일어날까요

sait2000 4년 전 3

예를 들면 이런 거요

in:
1
150
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
50
50
49
49
48
48
47
47
46
46
45
45
44
44
43
43
42
42
41
41
40
40
39
39
38
38
37
37
36
36
35
35
34
34
33
33
32
32
31
31
30
30
29
29
28
28
27
27
26
26
25
25
24
24
23
23
22
22
21
21
20
20
19
19
18
18
17
17
16
16
15
15
14
14
13
13
12
12
11
11
10
10
9
9
8
8
7
7
6
6
5
5
4
4
3
3
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
49
49
49
49
49
49
49
50

out:
0

seilk 2년 전 0

@sait2000

덕분에 문제 잘 해결했습니다. 감사합니다

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

문제

문제

출처

ICPC

어느 부분에서 시간을 더 줄여야 코드가 패스가 될까요?

atlanboa 4년 전 0

sait2000 4년 전 1

sait2000 4년 전 3

seilk 2년 전 0

@sait2000

덕분에 문제 잘 해결했습니다. 감사합니다

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말