greentec   2년 전

예제 입력은 맞는데 제출하면 틀리네요...

처음 한 개만 받을 수 있을지 질문드려봅니다.

baekjoon   2년 전

테스트 케이스는 제공하지 않습니다.

죄송합니다.

질문 글을 올리시면, 어떤 부분에서 틀렸는지 알려드릴 수 있습니다.

greentec   2년 전

네;; 아래와 같습니다.

baekjoon   2년 전

4 4
9 8 7 6
8 7 6 5
7 6 5 4
6 5 4 3

이런 데이터를 넣으면 틀리네요.

greentec   2년 전

아, 그렇군요;; 감사합니다!

greentec   2년 전

코드를 간결하게 만들어서 위 테스트 케이스는 통과했는데 시간초과가 걸리네요;

백트래킹을 써야 하는 건가요?

appa   2년 전

입력으로 들어오는 수들 중, 작은 수부터 보면서 동적계획법을 사용해주시면 됩니다. 시간복잡도는 정렬하는 데 걸리는 시간 O(N^2 log N^2)에 동적계획법을 수행하는 데 걸리는 시간 O(N^2)을 더해서 O(N^2 log N)이 됩니다.

baekjoon   2년 전

위의 방법으로 해도 되고, DFS를 이용해서 중복된 값을 계산하지 않게 Memoization을 사용할 수도 있습니다. 이 방법의 복잡도는 O(N^2)이 됩니다.

greentec   2년 전

음;; 그래프를 만들어서 갔던 길이 막혀 있는 곳이고, 그 길이 아니면 없애버리는 방법을 썼는데도 일단 계속 시간 초과가 나오네요..

아무래도 도와주시는 부분을 제가 잘 이해하지 못하는 것 같네요. 

조금 더 고민해 보겠습니다. 

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