lian   11달 전

계속 시간초과 뜨다가... 몇 개 멍청한 실수등을 발견하여 코드를 조금 더 수정하였더니

진행중 50%까지 올라가다가 틀렸습니다가 뜹니다.

------------------------------------------------------------------------------------------------------------------

코드 설명해보겠습니다.

먼저 각 노드에 대한 건설시간을 d[]라는 배열로 받았습니다.

그리고 x가 건설되어야 y가 건설된다는 개념으로 x, y 변수를 선언해서

order[y] = x 형태로 저장했습니다.

그리고 이렇게 저장할 때 order[y]에 한번이라도 어떤 값이 대입되었으면, (즉, order[y] = x가 한번이라도 수행되었으면,)간

d[order[y]] (이미 저장된 값의 건설시간)와 d[x] (현재 입력으로 받은 노드의 건설시간)을 비교해서 큰 쪽을 집어 넣도록 했습니다.


가령 예를 들자면,

문제에서 주어지는 두 번째 테스트 케이스의 경우,

1 ( 테스트 케이스 개수 T = 1)

8 8 (N = 8, K = 8)

10 20 1 5 8 7 1 43 (d 배열을 초기화 하고 이 값들을 d 배열에 저장함)

1 2 ( order[2] = 1)

1 3 ( order[3] = 1)

2 4 ( order[4] = 2)

2 5 ( order[5] = 2)

3 6 ( order[6] = 3)

5 7 ( order[7] = 5)

6 7 ( order[7]에 저장하려고 보니 이미 5가 저장되어 있으므로 d[order[7]]과 d[6]을 비교해 봅니다. 그러면 d[order[7]]이 8이어서 d[6]보다 크므로 order[7]을 6으로 변경하지 않고 5로 유지합니다.)

7 8 ( order[8] = 7)

7 ( w = 7 )


이렇게 하고 나면, cost 변수에다가 d[w]부터 순서대로 더해나갑니다.

w는 7이니까, d[7]을 먼저 더하고 그 다음 d[order[7]]을 더하고, 그 다음 d[order[order[7]]]을 더하는 방식을 취했습니다.

물론 order[order[...[order[w]]...]] 값이 없을때까지 덧셈을 진행합니다.



이런 방식으로 문제를 풀었는데, 틀렸다고 합니다.ㅠ


1005번에 대한 질문 읽어보니까 틀렸다고 뜨시는 분들은 출발점이 여러개인 경우에 대해서 틀렸다고 뜨는거 같은데,

그런 경우를 테스트 해봤으나 틀리진 않더라구요.


도와주세요~!

ilbbke   11달 전

1
5 4
10 1 100 10 1000
5 2
1 3
2 4
3 4
4

이 데이타요~

lian   11달 전

아... 문제의 원인을 드디어 알았네요.ㅠ.. 감사합니다.

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