인프런 커뮤니티 질문&답변

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

안녕하세요 자르트님 ㅎㅎ

꼭 등차수열의 합을 이용해야한다. 라기 보다는

직접 이런 경우의 수가 있네 이거 몇개일까?

라고 그려보다가 어? 이거 등차수열의 합으로 쉽게 구할 수 있겠네?

라고 접근하시는게 좋습니다.

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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.