절대 오버플로우 안 납니다. 각 T(n)에는 이론상 최대 109 + 8까지밖에 들어가지 않지만 long long의 최대는 1018 정도 되어 전혀 무리가 없으며, dp[]가 int형이긴 하지만 어차피 계산 후 결과는 109 + 9보다 작기에(int 형의 최대는 231 - 1, 대략 2*109 정도입니다.) 오버플로우가 날 일이 없습니다.
그나저나 T(n- 1) + T(n - 2)을 한 후 모듈러 연산을 해 주시고, 거기다 다시 T(n - 3)을 더한 후 모듈러 연산을 해 주시면 int형도 오버플로우가 나지 않습니다.
larpore2 1년 전
안녕하세요, 제출 전에 Dev C++에서 돌려봤는데 100000을 입력하니까 오버플로우 나더라구요.
그래서 제출해도 틀렸을거 같은데 수정할 부분이 어디인지 잘 모르겠습니다. long long해도 오버플로우가 나는거면 다른 방법이 있을까요?