2574번 - 마법색종이
안녕하세요!
분할정복으로 2574번 구현해서 ACC를 받았는데요
Worst case에선 O(n^2) 시간복잡도가 나오는 것 같은데 ACC가 나와서 의아했습니다
예를 들어,
40000 40000
30000
1 1
1 2
2 2
2 3
3 3
3 4 ....
이런 식으로 진행되는 testcase에서 제 코드는 O(n^2) 시간복잡도를 갖는데,
n <= 30000이면 O(n^2)가 1초 안에 작동된다고 생각해도 무방한가요?
아니면 실제 testcase엔 이런 worst case는 반영이 안 된건가요?
감사합니다!
댓글을 작성하려면 로그인해야 합니다.
naong606 8년 전
안녕하세요!
분할정복으로 2574번 구현해서 ACC를 받았는데요
Worst case에선 O(n^2) 시간복잡도가 나오는 것 같은데 ACC가 나와서 의아했습니다
예를 들어,
40000 40000
30000
1 1
1 2
2 2
2 3
3 3
3 4 ....
이런 식으로 진행되는 testcase에서 제 코드는 O(n^2) 시간복잡도를 갖는데,
n <= 30000이면 O(n^2)가 1초 안에 작동된다고 생각해도 무방한가요?
아니면 실제 testcase엔 이런 worst case는 반영이 안 된건가요?
감사합니다!