백준: Class 6 - 1086

</br> 클래스 6 계속
</br>

1086: 박성원

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

#include <bits/stdc++.h>

using namespace std;

vector<string> nums;
int rem[16];
int n, k;
long long dp[1<<15][101];
int dp2[51];

long long gcd(long long a, long long b){
    if( b > a ) return gcd(b, a);
    if( a%b == 0 ) return b;
    return gcd(b, a%b);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        nums.push_back(s);
    }
    cin >> k;
    if( k == 1 ){
        cout << "1/1" << '\n';
        return 0;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < nums[i].size(); j++){
            rem[i] = (rem[i]*10 + nums[i][j]-'0') % k;
        }
    }

    dp2[0] = 1;
    for(int i = 1; i <= 50; i++){
        dp2[i] = (dp2[i-1] * 10) % k;
    }

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int bit = 0; bit < (1<<n); bit++){
        for(int i = 0; i < n; i++){
            if( bit & (1<<i) ) continue;
            int b = bit | (1<<i);
            for(int j = 0; j < k; j++){
                int r = (rem[i] + ((j * dp2[nums[i].size()]) % k)) % k;
                dp[b][r] += dp[bit][j];
            }
        }
    }

    long long c = dp[(1<<n) - 1][0];
    if( c == 0 ){
        cout << "0/1" << '\n';
        return 0;
    }
    long long p = 1;
    for(int i = 2; i <= n; i++){
        p *= i;
    }
    long long cpgcd = gcd(c, p);

    cout << c/cpgcd << '/' << p/cpgcd << '\n';

}

알고리즘은 대충 알았는데 dp로 어떻게 할 지를 고민했다
dp[비트셋][나머지] = 경우의 수로 했다.
일단 50자리면 수가 굉장히 크기 때문에, 나머지를 그냥 %로 구할 수 없다. 따라서 한 자리 수씩 보면서 구했다.

만약 수가 12345라면
1*10000 + 2*1000 + 3*100 + 4*10 + 5 이므로
1. 1%k
2. ((1%k) * 10 + 2) % k. 즉 12%k
3. ((12%k) * 10 + 3) % k. 즉 123%k
...
이런 식으로 계산

그리고, 수가 계속 옆에 붙기 때문에, 그 자리수만큼 또 곱해 줘야 한다.

123 + 45해서 12345라면
123*100 + 45와 같으므로
( ((123%k)*100)%k + 45 ) % k로 (12345 % k)를 구할 수 있음

마지막 출력은 (구한 경우의 수) / (전체 경우의 수)를 기약분수로 나타내므로, gcd를 구해서 나눠주면 된다.
</br>

1708: 볼록 껍질

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

#include <bits/stdc++.h>
#define P pair<long long, long long>

using namespace std;

P points[100001];
P start;

int ccw(const P &p1, const P &p2, const P &p3){
    long long sa = p2.first*p1.second + p3.first*p2.second + p1.first*p3.second
            - p1.first*p2.second - p2.first*p3.second - p3.first*p1.second;
    if( sa > 0 ) return 1;
    if( sa == 0 ) return 0;
    return -1;
}

bool ccwcmp(const P &p2, const P &p3){
    int d = ccw(start, p2, p3);
    if( d == 1 ) return true;
    if( d == -1 ) return false;
    return p2.first*p2.first + p2.second*p2.second < p3.first*p3.first + p3.second*p3.second;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        points[i] = make_pair(a, b);
    }

    sort(points, points+n);
    start = points[0];
    sort(points+1, points+n, ccwcmp);

    stack<P> st;
    st.push(points[0]);
    st.push(points[1]);

    for(int i = 2; i < n; i++){
        while( st.size() >= 2 ){
            P b = st.top();
            st.pop();
            P a = st.top();
            int d = ccw(a, b, points[i]);
            if( d == 1 ){
                st.push(b);
                break;
            }
        }
        st.push(points[i]);
    }

    cout << st.size() << endl;

}

가장 기본적인 컨벡스 헐 문제
일단 점들을 정렬해서 x, y가 가장 작은 점은 바깥에 있을 게 당연하기 때문에 거기서 시작한다.
그 첫 점을 기준으로 각도 정렬을 한다.
각도가 작은 순으로 했으므로 첫 점과 그 다음 점을 이으면 오른쪽으로 갈 것이다. 그리고 이제 탐색을 시작한다. 만약 시계 방향으로 꺾이면, 볼록 다각형이 아니게 되므로 틀린 길이다. 따라서 두번 째 점을 지우고 더 바깥쪽에 있는 지금 보고 있는 점을 넣는다.
</br>

---

백신 맞고 근육통이 심해서 며칠 쉬었다
</br>