5-G while(1)문 내부를 이렇게 하면 왜 안될까요?

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

5-G

작성

239

수정됨

if(hi==p)break;
if(sum<n)sum+=a[hi++];
else sum-=a[lo++];
if(sum==n)ret++;

왜 순서를 바꾸면 오류가 날까요?

답변 2

반례 n = 3
while문

첫번째, hi = 1, p = 2 sum = 2
두번째, hi = 2, p = 2 sum = 5

sum이 크면 sum의 값을 줄인 후 다시 같은지 체크해줘야 하는데 체크하기 전에 이미 hi가 p 위치에 도착해 있어서 끝나는 것 같습니다 🙂
그래서 결국 ret이 1이 나와야 하는데 ret++을 하지 못하고 0으로 그대로 빠져 나와버려요.

지식공유자

안녕하세요 현성님 ㅎㅎ

사실 정확히는 다음 코드들과 비교해야 합니다.

    while(1){ 
        if(hi == p)break;
        else if(sum >= n) sum -= a[lo++];
        else sum += a[hi++];
        if(sum == n) ret++;
    }

이것과

    while(1){
        if(sum >= n) sum -= a[lo++];
        else if(hi == p)break;
        else sum += a[hi++];
        if(sum == n) ret++;
    }

이것인데요.

차이점이 좀 있는데 다음과 같습니다.

hi 가 ++ 한경우 -> hi == p break 가 되어야 하는데

hi 가 ++ 한경우 -> sum을 먼저 체크해서 break가 안되는 경우의 수가

발생합니다.

다만 해당 부분에 대한 반례는 못찾아서 찾으면 다시 답변 드리겠습니다.

감사합니다.

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