최소 공배수 처리 후, 각 재료 질량에 최대 공약수가 존재하게 되어 "재료의 질량을 모두 더한 값이 최소" 조건을 만족하지 않는 것으로 보입니다.
예를 들어)
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 하실 것으로 보입니다.
leekt321 6년 전
안녕하세요
1033번 문제 4%부터 틀렸습니다가 출력되는 걸 보니, 아무래도 제가 아예 고려하지 않은 조건 자체가 있는 것 같습니다.
풀이 구현은, 모든 N개의 정점을 그래프로 만들고, 방향성 간선에 무게로 비율을 저장했습니다. 역방향은 ^-1 취한 무게를 저장했구요.
그리고 모든 정점 N개가 이어져있다는 조건이 있다고 생각하고, 0에서 시작해서 bfs를 통해 그래프를 순회하면서 각 정점까지의 무게값.
즉 0에서부터의 어떤 정점까지의 무게를 계산해서 저장합니다(분모는 분모대로 곱하고 분자는 분자대로 곱하고)
이후 생성된 무게 배열을 한번 돌면서 각 무게를 최소화합니다.(분모와 분자를 최대공약수로 나눔)
그리고 생성된 최종 무게 배열에서 각 분모들의 최소공배수를 찾아서(N이 최대 9이므로, 대충 10000이하로 루프를 돌렸습니다) 마지막 값을 계산합니다.
제가 작성했던 TC에서는 정상출력이 된다고 생각했는데, 제가놓치고 있는 큰 조건이 있는것 같습니다.
혹시 해당 조건이 무엇인지, 그리고 그 조건에 대한 대응법을 알려주시면 감사하겠습니다.