zihasoo   10달 전

시간 초과가 계속 떠서 인터넷 검색을 하였는데 저와 거의 비슷한 풀이로 통과한 코드를 발견하였습니다. 

유일한 차이는 나머지를 구하는데 %를 사용하지 않았다는 것이었는데, 정말 놀랍게도 저 부분을 변경하자마자 맞게 되었습니다.

700ms가 나온 것을 보면 최소한 300ms이상 차이가 난다는 것인데, 몇백ms차이가 날 정도로 그렇게 큰 부분인가요? 그리고 저렇게 꼼수(?)를 써야 풀리는 것이면 이 풀이가 잘못된 것인가요? 재귀 DP로 풀었습니다.

정말 궁금합니다.


% 사용으로 시간초과한 코드

%를 -=로 대체한 코드

djm03178   10달 전

우선 나머지 연산은 무지하게 느린 연산이 맞습니다. 이 코드라면 아마 나머지 연산을 한 코드는 2초 이상도 충분히 걸렸을 수 있지 않을까 싶네요.

나머지 연산은 너무 느리기 때문에, m에 const 한정자를 추가하면 컴파일러가 이 연산을 나머지 연산이 아닌 더 가벼운 연산들 여럿으로 쪼개주기 때문에 아슬아슬하게 통과할 정도는 됩니다.

이 문제는 상태마다 최대 26번 루프를 돌리지 않고 푸는 방법이 있기 때문에 이 코드가 의도된 풀이는 아닐 거라 생각됩니다.

zihasoo   10달 전

그렇군요.... 
하지만 다시 풀기엔 너무 귀찮네요 나중에 재채점 터지면 다시 도전하겠습니다
감사합니다

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