[3-G 질문] 오버플로우 다르게 확인 하는 법..

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-G 와 테스트케이스 팁

해결된 질문

작성

427

안녕하세요 큰돌님!

덕분에, 코테도 준비하며 강의도 잘 보고 있습니다.

http://boj.kr/320a351402cb451d8aff7a538e73189d

3-G 문제를 공부하면서 질문이 있습니다.

Q1. 오버플로우 확인 할 때, 이렇게 작성하면 어떤 문제가 생기나요?
visited[next] == visited[here]+1 과 같이, 소모되는 시간이 같은 경우도, 동일한 cnt[]에 누적해야 한다는 로직은 이해했지만 코드로 옮기기 어려워서 질문드립니다 ㅠ

*링크 내의 아래와 같이 적힌 부분이 질문입니다.
if(next < 0 || next >= MAX || visited[next]) continue;
visited[next] = visited[here] + 1;
cnt[next] += cnt[here];
...
if(visited[next] == visited[here]+1)
cnt[next] += cnt[here];

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 진살라진님 ㅎㅎ

            if(next < 0 || next >= MAX || visited[next]) continue;
            visited[next] = visited[here] + 1;
            cnt[next] += cnt[here];
            q.push(next);
            if(visited[next] == visited[here] + 1) cnt[next] += cnt[here];

이렇게 작성하시면 안됩니다.

오버플로 + VISITED를 체크하는 거기 때문에 이 문제는 방문되었던 지점이라도 다시 방문해야 하는 순간이 있기 때문에 이렇게 하시면 안되구요.

이렇게 작성하시는게 좋습니다.

            if(next < 0 || next >= MAX) continue;
            if(!visited[next]){
                visited[next] = visited[here] + 1;
                cnt[next] += cnt[here]; 
                q.push(next);
            }else if(visited[next] == visited[here] + 1){
                cnt[next] += cnt[here];
            }

감사합니다.

욕망의햄버거

질문자

답변 감사합니다!
피드백 주신 코드를 보고 나서 이해가 되었습니다...!

인프런 커뮤니티 질문&답변

[3-G 질문] 오버플로우 다르게 확인 하는 법..