백준: Gold5 - 2225, 2229, 2230

계속

2225: 합분해

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

0 ~ N의 정수 K개를 더해서 합이 N 만드는 경우의 수

#include <bits/stdc++.h>
#define MOD 1000000000

using namespace std;

int dp[201][201];

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

    int n, k;
    cin >> n >> k;

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

    dp[0][0] = 1;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j < k; j++){
            for(int a = 0; a <= n; a++){
                if( i+a > n ) break;
                dp[i+a][j+1] = (dp[i+a][j+1] + dp[i][j]) % MOD;
            }
        }
    }
    cout << dp[n][k] << endl;

}

처음 보고 딱 떠오른 건 완전탐색… 근데 브랜치 앤 바운드 해도 시간 초과 날 게 뻔하겠어서 dp로 했다

dp[i][j]: 정수 j개를 더해서 합 i를 만드는 경우의 수

dp[i+a][j+1] += dp[i][j]

dp[i][j]가 경우의 수이므로, 여기에 어떤 정수 a를 더한 경우의 수는 dp[i+a][j+1] += dp[i][j]로 구할 수 있다.

2229: 조 짜기

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

주어진 배열을 적당히 잘라서 조 짜기
각 조 안의 (최댓값 - 최솟값)들의 합이 최대가 되어야 함

#include <bits/stdc++.h>

using namespace std;

int arr[1001];
int dp[1001];

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

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    for(int i = 0; i < n; i++){
        int ma = arr[i];
        int mi = arr[i];
        for(int j = i-1; j >= 0; j--){
            ma = max(ma, arr[j]);
            mi = min(mi, arr[j]);
            dp[i] = max(dp[i], dp[j-1] + ma - mi);
        }
    }
    cout << dp[n-1] << endl;
}

얘도 dp

dp[i]: i까지 구할 수 있는 조 나누기 점수 최댓값

dp[i] = max(dp[i], j-1번째까지 조 나누기 점수 최댓값 + j~i를 한 조로 했을 때의 그 조의 점수)
      = max(dp[i], dp[j-1] + j~i에서 최댓값 - j~i에서 최솟값);

여기서 j~i에서 최댓값과 최솟값을 어케 구하지?? 했는데 for(int j = i-1; j >= 0; j--) 이렇게 for문을 반대로 돌아서 j~i를 점차 늘려주면 최댓값과 최솟값을 알맞게 갱신할 수 있다.

2230: 수 고르기

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

수열에서 아무렇게나 수 2개를 골라서(중복 가능) 그 차가 M 이상이면서 가장 작은 차이 구하기

#include <bits/stdc++.h>

using namespace std;

int arr[100001];

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

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    sort(arr, arr+n);

    int ans = 2000000001;
    int l = 0, r = 0;
    while( l <= r && 0 <= l && r < n ){
        int k = arr[r] - arr[l];
        if( k >= m ){
            l++;
            ans = min(ans, k);
        }
        else if( k < m ) r++;
    }

    cout << ans << endl;
}

아무렇게나 고를 수 있어서 순서는 상관 없으니 정렬을 하면 되겠다
그러면 투 포인터 쓰면 끝이겠네~~ 오름차순으로 정렬 했으므로, 두 포인터의 차가 m보다 같거나 크면 l을 오른쪽으로 옮겨서 차를 줄이고, m보다 작으면 r을 오른쪽으로 옮겨서 차를 크게 한다.
얘는 풀이 자체는 바로 생각하고 구현했는데, 같은 수를 고를 수 있다는 걸 고려 안해서 한 번 틀렸다

---

굿