1-K 주몽 문제 재귀를 이용한 조합으로 푸는 방법

안녕하세요 룰루님 ㅎㅎ

모범 답안을 확인할 수 있을까요? 저도 풀 때 선생님이 푸신 것 처럼 이중 포문을 이용해서 했었는데, 재귀를 이용해서 푸는 방법도 궁금합니다.
>>

해당 풀이는 다음과 같습니다. 이렇게 하시면 됩니다. ㅎ

#include <bits/stdc++.h>
using namespace std;

int n, m, a[15001], cnt;

void print(vector<int>& b) {
    if (a[b[0]] + a[b[1]] == m) {
        cnt++;
    }
}

void combi(int start, vector<int>& b) {
    if (b.size() == 2) {  
        print(b);
        return;
    }
    for (int i = start + 1; i < n; i++) {
        b.push_back(i);
        combi(i, b);
        b.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    cnt = 0;
    vector<int> b;
    combi(-1, b);  
    cout << cnt << "\n";

    return 0;
}

또한, r이 3 이하일 경우 무조건 이중 for문으로 돌리는게 시간복잡도가 재귀보다 낮게 나오나요?

>> 시간복잡도가 같더라도 재귀보다는 반복문의 프로그램의 실행시간이 보통은 낮습니다.

이문제의 경우도 앞의코드 기반으로 풀었을 때는 다음과 같이 실행시간이 높게 나오는 것을 볼 수 있습니다.

그리고 다음부터는 해당 문제 - 질문에 매핑해서 질문 부탁드립니다.

그래야 좀 더 답변드리기가 쉽습니다.ㅎㅎ

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

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

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.
제공해드린 정보 내에서는 프로그래밍 강의 내용에 대한 상세한 설명이나 모범 답안에 관한 내용은 포함되어 있지 않습니다. 제공된 정보는 강의 이용 관련 일반적인 질문(기기 등록, 수강 기한, 멘토링 서비스, 할인 및 쿠폰 적용 여부 등)에 대한 답변으로 구성되어 있습니다.

재귀를 이용한 문제 풀이 방법이나 특정 시간 복잡도에 대한 질문은 강의의 Q&A 섹션이나 해당 내용을 다룬 프로그래밍 커뮤니티를 통해 더 구체적인 도움을 받으실 수 있을 것 같습니다.

재귀와 이중 for문의 시간복잡도 비교는 구현 방법과 문제의 조건에 따라 달라질 수 있으며, 일반적으로 재귀가 더 깊이 들어갈수록 추가적인 메모리 사용과 함께 오버헤드가 발생할 수 있어, 간단한 경우에는 이중 for문이 더 효율적일 수 있습니다. 그러나 이는 특정 문제 상황과 구현 방식에 따라 달라질 수 있어, 직접 비교하면서 성능을 테스트해보는 것이 좋습니다.