77dptjd   4년 전

https://77dptjd.tistory.com/20

문제에서 원하는 풀이는 저게 아닌거 같은데 AC받더라고요. 정말 모르겠으면 참고해보세용..

메모리 제한이 더 타이트해지거나 테케 추가되면 틀릴 수도 있을 거 같습니다.

herdson   4년 전

블로그에 언급하신 시간 복잡도는 O(N4 + K)입니다.

2504는 약 39억이 나오는데 실제론 b 크기에 따라 계산을 하지 않는 부분이 있어 더 적게 나옵니다. CPP 기준 연산을 아주 빠르게 하면 1초에 10억도 되므로 O(N4 + K)로도 문제 해결이 되리라는 추정을 할 수 있습니다.

저도 해봤는데 48ms 찍힌거 봐서는 이 문제는 일단 이렇게 풀어도 되고 P5만큼의 풀이가 나오려면 시간 제한을 0.01초로 줄이던지 행렬의 크기가 더 커야 합니다.

77dptjd   4년 전

오 왜 그런지 정확하게 몰랐는데 알려주셔서 감사합니다 :)

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