백준: Silver5① - 1010, 1037, 1059

</br> 백준이 현재 실버 5~~

티어를 올려 봐야 겠다. 앞에 등록된 문제일 수록 많은 사람들이 풀고 고치고 퀄리티가 좋을 확률이 높을 거니까, 티어가 오를 때까지 번호 순으로 풀어 보기로 한다.

지금은 쉬운 구간이니 좀 어려웠던 부분만 짚으면서…
</br>

1010: 다리 놓기

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

문제 보면 그냥 조합 구하기다.
그런데 그냥 n! / r!(n-r)! 하면 안 된다. 오버플로우 엄청 난다…

void fact(int a){
    if( a == 0 ) v0.push_back(1);
    else{
        v0.push_back(a);
        fact(a-1);
    }
}
void fact2(int a, int b){
    if( a == 0 || b == 0 ) v1.push_back(1);
    else{
        v1.push_back(a);
        fact2(a-1, b-1);
    }
}

for(int i = 0; i < n; i++){
        v1.clear(); v0.clear();
        unsigned long long a, b;
        cin >> a >> b;
        fact2(b, a); fact(a);
        int k = 1;
        for(int v : v1){
            k *= v;
            for(int i = 0; i < v0.size(); i++){
                if( k % v0[i] == 0 ){
                    k /= v0[i];
                    v0[i] = 1;
                }
            }
        }
        cout<<k<<endl;
    }

사람이 계산할 때처럼, v1에 분자, v2에 분모를 저장한 다음 약분하는 식으로 계산했다.
ex: 6C3) v1 = {6, 5, 4}, v2 = {3, 2, 1}
</br>

1037: 약수

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

1과 자기 자신을 뺀 모든 약수들로 어떤 수인지 맞추기

    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());

    cout << v[0]*v[v.size()-1] << endl;

간단하게~~ 약수들 정렬해서 처음 약수와 끝 약수를 곱하면 나오겠지~ 했는데 진짜 그럼
ex: 36) after sort => 2, 3, 4, 6, 9, 12, 18 => 2*18 = 36
</br>

1059: 좋은 구간

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

집합 사이에서 어떤 수를 포함하는 모든 구간 개수 구하기.

    sort(v.begin(), v.end());


    int cnt = 0;
    for(int i = 0; i < v.size(); i++){
        if( v[i] > k ){
            cnt = (k - v[i-1]) * (v[i] - k) - 1;
            break;
        }
        else if( v[i] == k ){
            break;
        }
    }

별 거 없고 또 정렬한 다음, k를 끼우는 두 숫자를 찾는다.
예로 보면 쉬워서 ex: 2, 10 사이 k=5) 3, 4, (5), 6, 7, 8, 9

5보다 작은 3과 4는 5~9까지를 포함하는 구간들 [3, 5, 6, … 9]
[4, 5, 6, … 9]
이 있고,

5보다 큰 6, 7, 8, 9는 구간이 하나 씩 [5, 6], [5, 7], [5, 8], [5, 9] 이 있음

즉 3과 4가 5, 6, 7, 8, 9 가능하므로 2*5,
6, 7, 8, 9가 가능하므로 5-1
따라서 식 = 3*5 - 1
</br>

---

괜히 골드 풀어 보다 어려워서 말았는데 쉬워서 좋네…
조금씩 올리면 골드도 잘 풀리겠지
</br>