17213번 과일 서리

https://www.acmicpc.net/problem/17213

다시 한 번 풀어보고, 복습할 문제이다.

즉, 생각해볼 문제이다.

복습!

백트래킹으로 풀었다.

그런데 아래 두 코드가 시간 차이가 꽤 났다.

여하튼 핵심은 두 코드 모두

nHr을 n+r-1Cr = n+r-1Cn-1로 바꾼 후에 진행하는 것이다.

그런데 첫 번째 코든느 vector size로 인해 시간이 꽤 걸렸다.

vector의 size()가 시간이 꽤 걸리나보다.

정답이긴 하지만 시간이 오래 걸림

#include <bits/stdc++.h>
 
using namespace std;
 
int ans, N, M;
 
void c(vector<int> v, int idx)
{
    if (v.size() == M)
    {
        ++ans;
        return;
    }
 
    for (int i = idx; i <= N; i++)
    {
        v.push_back(i);
        c(v, i + 1);
        v.pop_back();
    }
}
 
int main(void)
{
    int n, r;
 
    scanf("%d %d", &n, &r);
    r -= n;
 
    N = n + r - 1;
 
    M = n - 1;
 
    vector<int> v;
 
    c(v, 1);
 
    printf("%d\n", ans);
 
    return 0;
}
 

정답

#include <bits/stdc++.h>
 
using namespace std;
 
int ans, N, M;
 
void c(int cnt, int idx)
{
    if (cnt == M)
    {
        ++ans;
        return;
    }
 
    for (int i = idx; i <= N; i++)
    {
        c(cnt + 1, i + 1);
    }
}
 
int main(void)
{
    int n, r;
 
    scanf("%d %d", &n, &r);
    r -= n;
 
    N = n + r - 1;
 
    M = n - 1;
 
    vector<int> v;
 
    c(0, 1);
 
    printf("%d\n", ans);
 
    return 0;
}