leekt321   2년 전

안녕하세요

1033번 문제 4%부터 틀렸습니다가 출력되는 걸 보니, 아무래도 제가 아예 고려하지 않은 조건 자체가 있는 것 같습니다.

풀이 구현은, 모든 N개의 정점을 그래프로 만들고, 방향성 간선에 무게로 비율을 저장했습니다. 역방향은 ^-1 취한 무게를 저장했구요.

그리고 모든 정점 N개가 이어져있다는 조건이 있다고 생각하고, 0에서 시작해서 bfs를 통해 그래프를 순회하면서 각 정점까지의 무게값.

 즉 0에서부터의 어떤 정점까지의 무게를 계산해서 저장합니다(분모는 분모대로 곱하고 분자는 분자대로 곱하고)

이후 생성된 무게 배열을 한번 돌면서 각 무게를 최소화합니다.(분모와 분자를 최대공약수로 나눔)

그리고 생성된 최종 무게 배열에서 각 분모들의 최소공배수를 찾아서(N이 최대 9이므로, 대충 10000이하로 루프를 돌렸습니다) 마지막 값을 계산합니다.

제가 작성했던 TC에서는 정상출력이 된다고 생각했는데, 제가놓치고 있는 큰 조건이 있는것 같습니다.

혹시 해당 조건이 무엇인지, 그리고 그 조건에 대한 대응법을 알려주시면 감사하겠습니다.

kosb15   1년 전

최소 공배수 처리 후, 각 재료 질량에 최대 공약수가 존재하게 되어 "재료의 질량을 모두 더한 값이 최소" 조건을 만족하지 않는 것으로 보입니다.

예를 들어)

input)

10
4 0 1 1
4 1 3 1
4 2 5 1
4 3 7 1
3 5 1 9
3 6 8 2
5 7 2 1
7 8 5 8
5 9 1 6


output)

420 140 84 60 420 540 15 270 432 3240 

잘못된 output)
840 280 168 120 840 1080 30 540 864 6480

--> gcd = 2 존재


"모든 질량 합의 최소" 조건을 추가하신다면 PASS 하실 것으로 보입니다.

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