백준: Gold5 - 2688, 2981

계속

2688: 줄어들지 않아

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

0 ~ 9 숫자로 n자리 수를 만들 때, 줄어들지 않는 수의 개수 구하기

#include <bits/stdc++.h>

using namespace std;

long long dp[65][10];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    for(int i = 0; i <= 9; i++){
        dp[1][i] = 1;
    }

    for(int i = 2; i <= 64; i++){
        for(int j = 0; j <= 9; j++){
            for(int k = j; k <= 9; k++){
                dp[i][j] += dp[i-1][k];
            }
        }
    }

    while( t-- ){
        int n;
        cin >> n;
        long long sum = 0;
        for(int i = 0; i <= 9; i++){
            sum += dp[n][i];
        }
        cout << sum << '\n';
    }

}

간단한 dp
n1n2n3n4의 경우 n1의 경우에 가능한 n2n3n4의 개수를 살펴 보면 된다.

dp[i][j: 0 ~ 9] = dp[i-1][k: j와 같거나 큰 숫자]

2981: 검문

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

숫자들이 있을 때 그 숫자들을 각각 M으로 나눈 나머지가 다 같은 M들 구하기

#include <bits/stdc++.h>

using namespace std;

int arr[101];

int gcd(int a, int 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);

    int n;
    cin >> n;

    int a = 0;
    int b = 0;
    cin >> a;
    for(int i = 1; i < n; i++){
        cin >> b;
        arr[i] = abs(b - a);
        a = b;
    }

    int gcdNum = arr[1];
    for(int i = 2; i < n; i++){
        gcdNum = gcd(gcdNum, arr[i]);
    }

    vector<int> v;
    for(int i = 1; i <= sqrt(gcdNum); i++){
        if( gcdNum % i == 0 ){
            v.push_back(i);
            if( i*i != gcdNum ) v.push_back(gcdNum/i);
        }
    }

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

    for(int i = 1; i < v.size(); i++){
        cout << v[i] << ' ';
    }

}

바로 안 풀려서 좀 당황함
각 수들의 차들의 약수를 구하면 된다.

---

굿