friendof865   4년 전

위상정렬문제라고 하길래 맨 아래에서(작은 수라는 뜻이 아니고 만들 수 있는 최종적인 값을 맨 위라고 가정했을 때의 의미입니다.)부터 dp의 값을 구했습니다. 방식은 BFS와 유사합니다.

진입차수가 1일 경우에 진입차수가 0(저장된)인 하위 값들을 비교하는 방식으로 짰습니다.

이차원배열은 기준을 세우기도 모호하고 계산이 오히려 증가할 것 같아서 활용하지 않았습니다.

공식(?)에 따라 맞추는 게 좀 힘드네요.


시간복잡도를 생각했을 때 O(N(N+K))를 넘지 않을 것 같은데.. 뭐가 문젠지 잘 모르겠습니다.

성실한 답변 부탁드립니다!!

djm03178   4년 전

O(N(N+K))면 무리입니다. 1초에 1억 번의 가벼운 연산 정도를 한계치로 본다면 NK가 1억인데, 각 케이스가 테스트 케이스 여러 개로 이루어져있기 때문에 아무래도 어렵습니다. O(N+K)에 푸는 방법을 생각하셔야 되고, 이런 방법을 썼을 때가 200ms 상당이 나올 정도로 케이스 수가 많습니다.

friendof865   4년 전

댓글 남겨주셔서 감사합니다^^

시간복잡도가 O(N+K)여야 한다는 말씀을 듣고 소스를 바꿔봤습니다.

이번에는 시간복잡도가 O(2*K)입니다.


그런데 이번엔 '틀렸습니다.'가 떴습니다ㅠㅠ 

예전 질문들과 거기에 달린 답변에 나타나 있는 테스트 케이스들은 전부 맞게 나옵니다. 그렇다면 예외가 있다는 뜻인데, 그게 뭔지 찾아주실 수 있을까요? 33퍼도 아니고 완전 극초반에 틀리는 것 같던데..

혹은 코드를 새로 짤 수 있는 아이디어가 있을까요?

성실한 답변 부탁드립니다ㅠㅠㅠ

djm03178   4년 전

2번을 돌리는 것으로는 다음과 같은 케이스를 커버할 수 없습니다. T 입력은 무시하고,

4 3

1 1 1 1

2 1

3 2

4 3

1

위상정렬을 하는 일반적인 방법에 대해서 알아보시는 게 좋을 것 같습니다. 방법으로는 DFS를 통해 방문하여, 방문이 완전히 끝나는 시점이 늦은 것들부터 처리를 하는 것이나, indegree가 0인 것들을 순차로 큐에 넣고 방문하는 방법 등이 있습니다.

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