5-g

Question

항상 답변 주셔서 감사합니다. lo hi가 작은 수 부터 시작한다면 lo~hi의 합이 n 보다 작은 경우 hi가 ++ 되는 것은 이해가 됩니다. 하지만 lo ---- hi 사이에 큰 차이가 있다고 가정할 경우 lo~hi의 합이 n 보다 크면 lo를 크게 하라고 하셨는데, hi를 크게 해주면 안되는 이유는 뭔가요?? lo~hi의 합이 n 보다 작으면 hi를 크게 하라고 하셨는데 lo를 작게 할 수 있지도 않나요?? else if (hi == p)break; 이 코드 의미를 좀만 더 자세히 설명 부탁드립니다.

큰돌 · Answer

안녕하세요 ㅎㅎ 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점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.