5-H

Question

그리디에서 정말 많이 헤매는 학생입니다..! 구간을 탐색하다가 만난 것을 다시 만나면 s를 하나 늘려주고 e를 s+1로 땡겨 다시 카운팅한다는 것은 알겠습니다만 마지막에 등차수열의 합은 왜 나오는지 모르겠습니다! 3 1 2 가 남았을 때 while문이 끝나고 3 1 2로 만들 수 있는 경우가 {3} {1} {2} {3,1} {3,2} {1,2} {3,1,2,} 따라서 등차수열의 합이다. 라는 말씀이실까요..? 왜 등차수열의 합이 여기서 나오는지 잘 모르겠습니다! 경우의 수를 구하는 문제인데 공차가 존재할 때 사용되는 등차수열의 합이 나오는 이유가 뭘까요... 그리고 1 2 3으로 가다가 1을 만나 1 2 3 1이 되는 경우 1을 버려야 하므로 1 2 3 (s = 0, e = 3인 상황입니다, 영상에선 4:13) 까지 세주고 ret에 (e-s)를 더한다. 이 말이 1 2 3까지 오면서{1}{1,2}{1,2,3}을 만났기 때문에 (e-s)를 더해준다는 말씀이실까요??

자르트 · Answer

이 접근법으로 가보니 이해가 쉽게 되네요 항상 빠른 답변 너무나 감사합니다 큰돌님 :) 어렵지만 강사님 믿고 열심히 따라가서 코테 꼭 성공해보겠습니다!

큰돌 · Answer

안녕하세요 자르트님 ㅎㅎ 꼭 등차수열의 합을 이용해야한다. 라기 보다는 직접 이런 경우의 수가 있네 이거 몇개일까? 라고 그려보다가 어? 이거 등차수열의 합으로 쉽게 구할 수 있겠네? 라고 접근하시는게 좋습니다.     3 1 2로 만들 수 있는 경우가 {3} {1} {2} {3,1} {3,2} {1,2} {3,1,2,} 따라서 등차수열의 합이다. 라는 말씀이실까요..? >> 네 맞습니다. 다만 {3, 2}는 빼야겠죠? 연속된 수니까요. 왜 등차수열의 합이 여기서 나오는지 잘 모르겠습니다! 경우의 수를 구하는 문제인데 공차가 존재할 때 사용되는 등차수열의 합이 나오는 이유가 뭘까요... >> 음.. 이렇게 생각하시면 되요. 1 + 2 + 3 + 를 쉽게 구하는 것은 초항이 1이고 등차가 1이고 n이 3인 등차수열의 합이죠? 여기서 저 숫자는 사실 조합의 갯수입니다. 즉, {3,1,2,} + {3,1}, {1,2} + {3} {1} {2} 이기 때문입니다. 마지막으로 조합의 경우의 수를 나열하고 해당 경우의 수의 합을 빨리 구하는 방법을 생각하자 >> 등차수열의 합 이렇게 된다고 보시면 됩니다. 그리고 1 2 3으로 가다가 1을 만나 1 2 3 1이 되는 경우 1을 버려야 하므로 1 2 3 (s = 0, e = 3인 상황입니다, 영상에선 4:13) 까지 세주고 ret에 (e-s)를 더한다. 이 말이 1 2 3까지 오면서{1}{1,2}{1,2,3}을 만났기 때문에 (e-s)를 더해준다는 말씀이실까요?? >> 네 맞습니다. 1이 되어서 1 2 3 1 을 조합을 놓을 수 없기 때문에 {1}{1,2}{1,2,3} 조합에 해당되는 수를 + 해야 해서 e - s를 더해주어야 합니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.