Q&A
이해되지 않는 부분이 있어서 질문드립니다.
저도 같은 질문으로 헷갈려서 계속 파고드느라 시간이 걸렸네요.. 새로 공부하시는 분들을 위해 쉽게 설명하자면, [1, 2, 3, 1, 3] M=6으로 예를 들 때, 강사님 설명처럼 우선 왼쪽 포인터를 0으로, 오른쪽 포인터를 2(값 3)까지 쭉 최대로(M 허용 범위까지) 옮기면 1(인덱스0)에서 나올 수 있는 경우의 수는 {1} 2(인덱스1)는 {2}, {2, 1} 3(인덱스2)는 {3}, {3, 2}, {3, 2, 1} .... 이렇게 본인과 왼쪽에 있는 요소들을 한 번씩 포함한 집합들이 모이게 됩니다. [우측 포인터 기준으로 집합 구성해서 {3}, {3,2} 이런 식입니다] 여기서 저 집합들의 개수를 구하는 게 rt - lt + 1입니다. (배열 인덱스는 0번부터이므로 +1 처리) 다시 위 과정으로 돌아가서 가짓수 세는 라인을 추가하면, 1에서 나올 수 있는 경우의 수는 {1} (rt - lt + 1로 이 세이브포인트에서 가짓수 누적) answer = 1 2는 {2}, {2, 1} (rt - lt + 1로 이 세이브포인트에서 가짓수 누적) answer = 3 3은 {3}, {3, 2}, {3, 2, 1} (rt - lt + 1로 이 세이브포인트에서 가짓수 누적) answer = 6 ..... 따로 카운팅하지 않아도 M이 되지 않는 범위 안에서 포인터 양쪽을 쭈욱 늘리면 결국 한 번씩 돌면서 각각 가짓수를 저장하게 됩니다. 중요한건, 같은 수라고 이전에 계산한 조합들이랑 똑같은 애들이 아니예요. 앞에서 {1} , {1, 3} 이 있었다고 해도, 뒤에서 찾는 연속부분 {1} {1,3}과는 다른 존재로 칩니다. 이제 rt=3(값1)으로 한 칸 넘어가 봅시다. 일단 sum에 1을 더하면 |1,2,3,1|(인덱스 0~3)의 합이 7이 되어 M(6)을 초과합니다. 그래서 왼쪽(lt)을 한 칸 당겨줍니다 → lt=0에서 1로. 이제 |2,3,1|(인덱스 1~3), 합=6으로 M 이내가 됩니다. 이 시점(rt=3)에서 새로 추가되는 건, 끝점이 인덱스3(값1)인 부분배열들뿐입니다. {1}, {1,3}, {1,3,2} → 3개 rt - lt + 1 = 3 - 1 + 1 = 3 → answer = 6 + 3 = 9 다음 rt=4(값3)으로 옮기고, 옮겨서 for문 종료때까지 반복합니다. 헷갈릴 만한 부분은, 카운트를 따로 세지 않아도, 끝점, lt rt를 활용해서 범위 안에서 본인을 포함하는 수열들만 구해도 카운팅된다 는 점과, 앞에서 구한 수열과 뒤에서 찾은 수열은 다른 존재(중복되지않는 조합 구하는게 아님!) 라는 점입니다. 저도 결국은 말이 길어졌지만 헷갈리셨던 분들 이해에 도움이 됐으면 합니다 :)
- Likes
- 0
- Comments
- 2
- Viewcount
- 387