• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

5-g

23.11.24 12:13 작성 23.11.24 13:36 수정 조회수 100

0

항상 답변 주셔서 감사합니다.

lo hi가 작은 수 부터 시작한다면 lo~hi의 합이 n 보다 작은 경우 hi가 ++ 되는 것은 이해가 됩니다.

 

하지만 lo ---- hi 사이에 큰 차이가 있다고 가정할 경우

  1. lo~hi의 합이 n 보다 크면 lo를 크게 하라고 하셨는데, hi를 크게 해주면 안되는 이유는 뭔가요??

  2. lo~hi의 합이 n 보다 작으면 hi를 크게 하라고 하셨는데 lo를 작게 할 수 있지도 않나요??

  3. else if (hi == p)break; 이 코드 의미를 좀만 더 자세히 설명 부탁드립니다.

답변 1

답변을 작성해보세요.

0

큰돌님의 프로필

큰돌

지식공유자

23.11.25 07:34

안녕하세요 ㅎㅎ

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

이부분 말씀이시죠?

일단 lo, hi는 같은 정점에서 시작합니다.


        if(sum >= n) sum -= a[lo++];

만약 sum보다 n 이상입니다.

좀 더 줄여야하는 순간이며

맨 밑의 sum == n, 연속합이 자연수 n을 충족하는 것을 거치고 나서 while문 첫번째로 온 순간입니다.

1, 2, 3, 4라는 인덱스가 있다고 가정.

1 2 3 4

1, 3 이 lo, hi라고 보았을 때

이 때 lo를 ++해야 할까요? hi를 ++해야할까요?

만약 hi++를 하게 되면 이게 되겠죠?

1 2 3 4

이렇게 되면 2 3이라는 경우의 수는 확인하지 못합니다.

그러나 2 3이라는 경우의 수는 좀 더 작은 경우의 수입니다.

 

예를 들어

2 3 5 7 11이라고 헀을 때

3 ~ 11 의 합인 상태인데 여기서 좀 더 적은 경우의 수는.

5 ~ 11 이기 때문입니다.

 

그래서 lo++해서 이렇게 먼저 확인을 합니다.

1 2 3 4

그래서 이 때 lo++를 합니다.

hi++은 그 반대이구요.

 

 

        else if(hi == p)break;

만약 p에 도달했으면 모든 경우의 수는 다 탐색을 한 것입니다.

p의 의미는 소수의 맨 오른쪽, 끝 점을 의미합니다.

예를 들어 2 3 5 7 이고 자연수가 15라고 했을 때

lo = 3, hi = 7 인 순간이겠죠?

2 3 5 7

이 때는 더이상 탐색할 경우의 수가 없습니다. 그래서 종료를 시킵니다. 그리고 sum == n부분은 이미 while문 맨끝에서 확인했기 때문에 더이상 뭘 할 필요가 없습니다.




또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.