3-A combi 메소드 시작 인덱스에 따른 시간초과 이유

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

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-A

해결된 질문

작성

203

수정됨

안녕하세요 큰돌님! 다름이 아니라, combi 메소드를 생성할 때,

for (int i = start; i < chicken.size(); i++) {
    arrayList.add(i);
    combi(i);
    arrayList.remove(arrayList.size() - 1);
}

이 부분에서 starting index를 0으로 하면 시간초과가 나는 반면,

starting index를 -1로 설정한 후

for (int i = start + 1; i < chicken.size(); i++)
{/*...*/}

이런 식으로 작성하면 문제없이 통과됩니다. -1에서부터 인덱스를 시작하면 combi 메소드를 호출하는 횟수가 0에서 시작하는 것보다 상당한 차이로 줄어드는데 혹시 그러한 이유를 알 수 있을까요..?

혹시 combi 내에서 호출할 때에 for문에서 int i의 시작점이 변화 없이 그대로 진행되기 때문일까요.. 감사합니다!

답변 1

지식공유자

안녕하세요 ㅎㅎ

for (int i = start; i < chicken.size(); i++) {
    arrayList.add(i);
    combi(i);
    arrayList.remove(arrayList.size() - 1);
}

이렇게 하게 되면

combi(0) -> combi(0) -> combi(0)

이런식으로 중복된 경우의 수가 생겨버리게 됩니다.

start부터 시작하게 되니까요.

그래서 그런 것 같습니다. ㅎㅎ

혹시 combi 내에서 호출할 때에 for문에서 int i의 시작점이 변화 없이 그대로 진행되기 때문일까요.. 감사합니다!

>> 네 맞습니다. ㅎㅎ

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

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

감사합니다.

강사 큰돌 올림.

작성한 질문수