gumdung   4년 전

안녕하세요.

질문을 올리기까지 정말 망설였는데 저에겐 버거운 문제라고 판단되어 이렇게 질문을 올립니다.

먼저 small 버전

https://www.acmicpc.net/problem/14505

이 문제를 풀고 나서 보고있는데 tle를 잡지를 못하고 있는 상황입니다....

저 문제도 사실 힌트를 얻어(포함배제의 원리) 간신히 풀었는데 정확한 시간 복잡도가 과연 어떻게 되는지도 모르겠더라구요.

그래서 아마 이 문제에서 tle가 발생하는 것 같은데 조금이나마 도움이 될 만한 조언들 감사히 여기겠습니다.

doju   4년 전

시간 초과가 나는 이유는 함수의 인자로 들어가는 string s가 함수를 호출할 때마다 복사되기 때문입니다. 이 코드에서 s는 전혀 변경되지 않으므로, 레퍼런스 형식(string &s)으로 전달하거나 아예 전역 변수로 놓는 등의 방법으로 개선할 수 있습니다.

gumdung   4년 전

@doju

정말 너무너무 감사드립니다. 생각하지도 못한 부분 때문에 시간초과가 발생한 것이었군요.

그리고 조심스럽게 질문을 조금만 더 하겠습니다.죄송합니다.

1.일단 s를 전역으로 선언한 후에도 틀렸습니다가 나왔습니다. 10007로 나누기 때문에 오버플로 문제도 없을텐데 어느부분에서 틀렸는지 잘 모르겠습니다.

2.또한 저가 개인적으로 저 코드의 시간복잡도를 생각했을때 대략 s의 길이만큼을 두번 탐색? 하여 O(n^2) 이 되지 않을까? 라고 생각이 들긴 하는데 확실한지 모르겠습니다 ㅠㅠ

답변 다시한번 진심으로 감사드립니다.

doju   4년 전

1. 코드를 수정한 뒤에는 수정된 코드를 다시 올려 주시면 좋습니다. 지금의 코드는 나머지 연산이 제대로 적용되어 있지 않습니다.

2. 시간복잡도는 O(n^2)이 맞습니다. 간단히 설명하면 DP 테이블에서 총 O(n^2)개의 칸에 값을 채워야 하고, 하나의 칸을 채울 때마다 go()가 상수 번(최대 4번) 호출되기 때문입니다.
여담으로, 몇몇 DP 문제에서는 중간 결과가 0이 되는 경우가 있기 때문에 if (dp[l][r]) return dp[l][r];과 같은 구문은 다소 위험합니다. 이 글을 참고해 보세요.

gumdung   4년 전

@doju

죄송합니다 너무 성급했던 것 같습니다.

제출한 소스는 이렇습니다. 

일단 doju님의 조언을 보고 전부 -1로 초기화를 시켜준다음에 실행을 하였습니다.

1.l>r 일때는 0

2.l==r일때는 1

외에는 재귀함수로 탐다운 방식으로 채워주었습니다.

또한 나머지 연산도 문제없이 처리를 해주었다고 생각되긴 하는데,,,,여전히 ac를 맞지 못하는 상황입니다.

좀 귀찮을정도로 여쭈어 봐서 정말 죄송합니다. 답변하기 불편하시다면 가볍게 무시해도 괜찮습니다.

감사합니다.

doju   4년 전

27번째 줄의 식에는 뺄셈이 있기 때문에 결과가 음수가 될 수 있습니다.

gumdung   4년 전

@doju

뭐라고 말씀드려야 할지 모를정도로 감사합니다.

문제 풀면서 수없이 포기하고 싶다는 생각이 들긴 하는데 doju님을 포함해서 다양한 분들이 도움되시는 말씀들 보면서 이악물고 어떻게서든 버티는 것 같습니다.

건강하시고 다시 한번 감사드립니다.

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