백준: Silver⑫ - 1716, 1463, 1654, 1699

</br> 실버 3에 유명한 문제만 좀만 더 보고 실버 2로 넘어가자
</br>

1716: Polynomial Remains

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

다항식 나눗셈에서 나머지 구하기

    while( !(n == -1 && k == -1) ){
        for(int i = 0; i < n+1; i++){
            int a;
            cin >> a;
            pol[i] = a;
        }
        for(int i = n; i >= k; i--){
            pol[i-k] -= pol[i];
            pol[i] = 0;
        }
        stack<int> st;
        for(int i = n; i >= 0; i--){
            if( pol[i] ) st.push(pol[i]);
        }
        if( st.empty() ) st.push(0);
        while( st.size() ){
            cout << st.top() << ' ';
            st.pop();
        }
        cout << '\n';
        cin >> n >> k;
    }

실버 5인데 못 풀었다가 이제 푼다
알고 보니까 입력이 x^n x^n-1 … 이렇게 안 들어오고 x^0 x^1 … 이렇게 들어와서 틀린 거였다 참내~~ 문제를 정말 꼼꼼히 봅시다
</br>

1463: 1로 만들기

https://www.acmcpc.net/problem/1463

시간 제한 안에 n을 1로 만들기

    for(int i = 0; i < n; i++){
        dp[i] = 1000001;
    }

    dp[n] = 0;
    for(int i = n; i > 1; i--){
        dp[i-1] = min(dp[i-1], dp[i] + 1);
        if( i % 2 == 0 ) dp[i/2] = min(dp[i/2], dp[i] + 1);
        if( i % 3 == 0 ) dp[i/3] = min(dp[i/3], dp[i] + 1);
    }

    cout << dp[1] << endl;

시간 제한이 0.15초인 dp 문제다
최소 횟수를 계속 업데이트해 주면 끝~~
</br>

1654: 랜선 자르기

https://www.acmcpc.net/problem/1654

랜선 최대한 길게 자르기

    long long l = 1, h = 0;
    for(int i = 0; i < k; i++){
        cin >> lan[i];
        h = max(h, (long long)lan[i]);
    }
    int ans = 1;
    while( l <= h ){
        long long mid = (l+h) / 2;
        int cnt = 0;
        for(int i = 0; i < k; i++){
            cnt += lan[i] / mid;
        }
        if( cnt < n ){
            h = mid-1;
        }
        else{
            ans = max(ans, (int)mid);
            l = mid+1;
        }
    }

    cout << ans << endl;

헉… 이분 탐색인데 low와 high를 long long으로 안 해서 틀렸다
길이가 1000000이하인 줄 알았는데 n의 크기가 저렇고 길이는 2^31-1이었다ㅜㅜ
</br>

1699: 제곱수의 합

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

n이 제곱수들 최소 몇 개의 합으로 이루어질까

    for(int i = 1; i*i <= n; i++){
        pows[i] = i*i;
    }
    for(int i = 1; i <= n; i++){
        dp[i] = INT_MAX;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j*j <= i; j++){
            dp[i] = min(dp[i], dp[i-pows[j]]+1);
        }
    }
    cout << dp[n] << endl;

간단한 dp
dp[i] = min(dp[i], dp[i-제곱수]+1들)
</br>

---

포스트는 하루 2개 정도씩 올려서 업로드가 꽤 밀리는 바람에 언제 올라갈 지 모르겠는데 현재 12일 연속 문제 해결 중이라네
꾸준하게 가야지
</br>