백준: Class 4 - 2407, 9465, 11053

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

2407: 조합

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

int n, m;
int hundreds[101];
string ans;

void mult(int p){
    int one = 0;
    int sz = ans.size()-1;
    for(int i = 0; i < sz+1; i++){
        int t = (ans[sz-i] - '0') * p + one;
        one = t/10;
        ans[sz-i] = t%10 + '0';
    }
    if( one ) ans.insert(0, to_string(one));
}
void primes(int k, int isMinus){
    int j = 2;
    while( k > 1 ){
        if( k % j == 0 ){
            hundreds[j] += isMinus;
            k /= j;
        }
        else j++;
    }
}

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

    cin >> n >> m;

    for(int i = 0; i < m; i++){
        primes(n-i, 1);
    }
    for(int i = 2; i <= m; i++){
        primes(i, -1);
    }

    ans = "1";
    for(int i = 0; i < 101; i++){
        if( hundreds[i] != 0 ) mult(pow(i, hundreds[i]));
    }
    cout << ans << endl;
}

답 자체가 엄청 큰 수가 나와서 long long으로도 감당이 안 되더라

ex) 100C50 = 100891344545564193334812497256

그래서 곱셈을 string으로 계산해 줘야 한다.
일단 hundreds[]에 소인수 분해한 것들의 개수를 표시했다.

ex) 6C3
분자 계산: 6*5*4
-> hundreds[2] = 3, hundreds[3] = 1, hundreds[5] = 1

분모 계산: 3*2*1
-> hundreds[2] = 3-1 = 2, hundreds[3] = 1-1 = 0, hundreds[5] = 1
-> hundreds[2] = 2, hundreds[5] = 1

따라서 답: 2^2 * 5^1

문자열로 곱셈 구현은 손으로 하듯이 했다

ex) 123456789 * 34
9*34 = 306        > 30 넘김, ans: 6
8*34 + 30 = 302   > 30 넘김, ans: 26
7*34 + 30 = 268   > 26 넘김, ans: 826
...
ans: 4197530826

은근 이런 게 재밌네
</br>

9465: 스티커

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

    while( t-- ){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> stickers[0][i];
            dp[0][i] = 0;
        }
        for(int i = 1; i <= n; i++){
            cin >> stickers[1][i];
            dp[1][i] = 0;
        }
        dp[0][0] = 0;
        dp[1][0] = 0;
        dp[0][1] = stickers[0][1];
        dp[1][1] = stickers[1][1];
        for(int i = 2; i <= n; i++){
            dp[0][i] = max(dp[0][i], dp[0][i-2]);
            dp[0][i] = max(dp[0][i], dp[1][i-2]);
            dp[0][i] = max(dp[0][i], dp[1][i-1]);
            dp[0][i] += stickers[0][i];
            dp[1][i] = max(dp[1][i], dp[0][i-2]);
            dp[1][i] = max(dp[1][i], dp[1][i-2]);
            dp[1][i] = max(dp[1][i], dp[0][i-1]);
            dp[1][i] += stickers[1][i];
        }
        cout << max(dp[0][n], dp[1][n]) << '\n';
    }

dp인데 뭔가 식을 바로 생각은 못해냈다
dp[0][i]를 i번째의 위쪽 스티커를 선택했을 때의 최댓값으로, dp[1][i]는 i번째의 아래쪽 스티커를 선택했을 때의 최솟값으로 했다.
그럼 현재 이 스티커를 선택하면, 가능한 조합은 내 바로 왼쪽을 제외한 것들일 것이다.

ex) 백준 예제, n = 5
50 10 100 20 40
30 50 70 10 60

dp
0 50 40  200
0 30 100  ??
??은 50, 30, 40 중 고를 수 있으므로 50 + 70 = 120이 되어야 함

</br>

11053: 가장 긴 증가하는 부분 수열

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

    int ans = 0;
    nums[n] = 1001;
    dp[n] = 0;
    for(int i = n-1; i >= 0; i--){
        for(int j = i+1; j <= n; j++){
            if( nums[j] > nums[i] ) dp[i] = max(dp[i], dp[j]+1);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;

이것도 dp 문제다. 이중 포문으로도 충분히 잘 돌아간다.
앞에서 하나 뒤에서 하나 상관은 없을 것 같다 dp[i] = max(dp[i], dp[증가하는 부분 수열을 만들 수 있는 수의 인덱스] + 1)

ex) 백준 예제
6                     // 쓰레기값 추가
p:  10 20 10 30 20 50 10001

dp:                   0
dp:                1  0
dp:             2  1  0
dp:          2  2  1  0   << 20 건너 뛰고, 맥스는 dp[50의 인덱스]+1
...
dp: 4  3  3  2  2  1  0

</br>

---

dp를 푸니 마음이 차분해 진다
</br>