1005번 - ACM Craft
계속 시간초과 뜨다가... 몇 개 멍청한 실수등을 발견하여 코드를 조금 더 수정하였더니
진행중 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번에 대한 질문 읽어보니까 틀렸다고 뜨시는 분들은 출발점이 여러개인 경우에 대해서 틀렸다고 뜨는거 같은데,
그런 경우를 테스트 해봤으나 틀리진 않더라구요.
도와주세요~!
15 410 1 100 10 10005 21 32 43 44
이 데이타요~
아... 문제의 원인을 드디어 알았네요.ㅠ.. 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
lian 8년 전
계속 시간초과 뜨다가... 몇 개 멍청한 실수등을 발견하여 코드를 조금 더 수정하였더니
진행중 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번에 대한 질문 읽어보니까 틀렸다고 뜨시는 분들은 출발점이 여러개인 경우에 대해서 틀렸다고 뜨는거 같은데,
그런 경우를 테스트 해봤으나 틀리진 않더라구요.
도와주세요~!