백준 재활 연습 - 1일차

이번에 KOI에서 잘 못해서 빡친 나는 이번년도에 코포 오렌지 달고 간다는 생각으로 재활훈련을 시작했다.

처음 셋은 조합론 + dp 조합이다.

운으로 올솔하였다.

 

1. www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

처음 봤을 때는 만만치 않은 문제처럼 보이나, 순서를 고려해주면 아주 쉽게 풀 수 있는 문제이다.

먼저 우리가 신경써야 할 것은 순서에 의한 중복되는 경우의 수인데, 순서를 어떤 기준을 세워서 나타내어 중복을 없앴다.

나는 이 식이 항상 내림차순으로 더한다고 기준을 정하였다.( ex) 5=3+2=3+1+1=2+2+1=2+1+1+1)

그리고 정의해주고 식만 세우면 아주 쉬운 문제가 되버린다.

dp[i][j] = 더해서 i가 되고 마지막으로 더한 숫자가 j일때 경우의 수

자세한 점화식은 기준을 확실하게 이해했다면 코드를 보고 바로 이해가 될 것이다.

#include <bits/stdc++.h>
#define MEM 10005
#define f first
#define s second
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll INF = 1e9+9;
ll n,y,c,t;
ll dp[MEM][3];
main(){
    sanic;cin.tie(0);
    dp[1][0] = 1;
    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[3][0] = 2;
    dp[3][2] = 1;
    for(int i=4; i<MEM; i++){
        dp[i][0] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
        dp[i][1] = dp[i-2][1]+dp[i-2][2];
        dp[i][2] = dp[i-3][2];
    }
    cin >> t;
    while(t--){
        cin >> n;
        cout << dp[n][0]+dp[n][1]+dp[n][2] << '\n';
    }
}

2. www.acmicpc.net/problem/2482

2482번: 색상환

전형적인 dp문제이다. ㅋㅋ

굳이 풀이를 하자면 

dp[i][j] = i개의 색상에서 j개 고를 때 경우의 수

로 캐이스를 따져 점화식을 세우면 된다.

자세한건 코드 참고.

#include <bits/stdc++.h>
#define MEM 1001
#define f first
#define s second
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9+3;
ll n,m;
ll dp[MEM][MEM];
main(){
    sanic;cin.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        dp[i][1] = i;
    for(int i=1; i<=n; i++)
        for(int j=2; j<=m; j++)
            if(j<=i/2)
                dp[i][j] = (dp[i-1][j]+dp[i-2][j-1]+MOD)%MOD;
    cout << dp[n][m];
}

3. www.acmicpc.net/problem/19535

19535번: ㄷㄷㄷㅈ

G-ㅈ을 만들기 위해서는 중심노드 하나와 중심노드의 degree가 3이상이어야 한다. 이때 연결되어 있는 노드들 중 3개를 고르는 경우의 수가 G트리의 갯수가 된다.

D-D트리는 선형으로 연결되어 있는 노드 3개따리 트리를 찾아야 한다. 일단 인접한 정점 두개를 잡은 뒤 각 노드의 degree-1을 곱한 것이 두 정점의 D트리를 만드는 경우의 수가 된다. 이를 모두 합한게 D트리의 총갯수가 된다.

따라서 트리를 만들어서 각 노드마다 degree를 구하여 G, D트리의 갯수를 구하면 된다.

자세한건 코드 참고.

#include <bits/stdc++.h>
#define MEM 300001
#define f first
#define s second
#define sanic ios_base::sync_with_stdio(0)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9+3;
ll n,m;
ll d,j;
vector<ll> g[MEM];
main(){
    sanic;cin.tie(0);
    cin >> n;
    for(int i=0; i<n-1; i++){
        ll u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1; i<=n; i++){
        ll f=g[i].size();
        j += (f*(f-1)*(f-2))/6LL;
        for(int l=0; l<f; l++){
            ll nt=g[i][l];
            if(i>nt) continue;
            d += (g[nt].size()-1)*(f-1);
        }
    }
    if(d>3*j) cout << "D";
    else if(d<3*j) cout << "G";
    else cout << "DUDUDUNGA";
}

 

스코어보드