Cộng đồng Hỏi & Đáp của Inflearn

câu hỏi đã được viết

Hoàn thành C++ Coding Test trong 10 tuần | Thuật toán Coding Test

5-G

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

Viết

270

Đã chỉnh sửa

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

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

c++코딩-테스트

Quiz

그리디 알고리즘의 기본적인 문제 해결 방식은 무엇일까요?

문제를 부분 문제로 나누어 해결한다.

각 단계에서 가장 좋아 보이는 선택을 한다.

모든 가능한 경우를 탐색한다.

과거 데이터를 분석하여 미래를 예측한다.

Câu trả lời 2

반례 n = 3
while문

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

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

Người chia sẻ kiến thức

안녕하세요 현성님 ㅎㅎ

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

    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가 안되는 경우의 수가

발생합니다.

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

감사합니다.

câu hỏi đã được viết