Problem Solving @ 2022/04/21

중간고사가 다가오네요. 그 와중에 PS를 하고 있습니다.

 

1. 숫자 박스 (G2) - KOI 2003 고등부 2번

 

시간 복잡도: O(N^3)

알고리즘: DP

 

Only DP 문제입니다. dp 테이블을 다음과 같이 나타냅시다.

 

≫ dp[idx][a][b] = idx까지 숫자를 설치했을 때, 1번째 줄의 박스를 a개, 2번째 줄의 박스를 b개 설치했을 때 최댓값

 

4가지 방법이 있습니다.

 

• 1번째 줄에 a번째 박스만 설치하기
• 2번째 줄에 b번째 박스만 설치하기
• 둘 다 설치 안하기
• 둘 다 설치하기

 

여기서 3번째 경우는 항상 손해이므로 배제해서, dp 테이블을 채워나갑니다. 예외 처리를 많이 해주어야 하는 것이 포인트입니다.

 

#include <iostream>
#include <algorithm>

using namespace std;
#define INF 999999999

int N, A = 1, B = 1;
int dp[401][401][401];
int aarr[401], barr[401];

int solve(int idx, int a, int b) {

  if (a == A + 1 || b == B + 1) return 0;

  int& cache = dp[idx][a][b];
  if (cache != -INF) return cache;

  if (N + a > idx + A) cache = max(cache, solve(idx + 1, a, b + 1));
  if (N + b > idx + B) cache = max(cache, solve(idx + 1, a + 1, b));
  cache = max(cache, solve(idx + 1, a + 1, b + 1) + aarr[a] * barr[b]);

  return cache;
}

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    int inp; cin >> inp;
    if (inp != 0) { aarr[A] = inp; A++; }
  }
  for (int i = 0; i < N; i++) {
    int inp; cin >> inp;
    if (inp != 0) { barr[B] = inp; B++; }
  }
  A--; B--;

  for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) for (int k = 1; k <= N; k++) dp[i][j][k] = -INF;

  cout << solve(1, 1, 1) << endl;
}

 

2. 누적 거리 (G2) - KOI 2021 2차대회 중등부 2번

 

설명은 사진 딱 한 장으로 충분합니다. 사진에서 psum은 누적 합이라는 뜻입니다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define int long long

int N, Q;

int pa[200001][2], pax[200001][2];
pair<int, int> ax[200001]; int x[200001];
signed main() {

  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  cin >> N >> Q;
  for (int i = 0; i < N; i++) {
    int a, xi; cin >> a >> xi;
    ax[i] = { xi, a }; x[i] = xi;
  }

  sort(ax, ax + N); sort(x, x + N);
  pax[0][0] = (int)(ax[0].first * ax[0].second); pa[0][0] = (int)(ax[0].second);
  for (int i = 1; i < N; i++) {
    pax[i][0] = (int)(ax[i].first * ax[i].second); pax[i][0] += pax[i - 1][0];
    pa[i][0] = (int)(ax[i].second); pa[i][0] += pa[i - 1][0];
  }
  pax[N - 1][1] = (int)(ax[N - 1].first * ax[N - 1].second); pa[N - 1][1] = (int)(ax[N - 1].second);
  for (int i = N - 2; i >= 0; i--) {
    pax[i][1] = (int)(ax[i].first * ax[i].second); pax[i][1] += pax[i + 1][1];
    pa[i][1] = (int)(ax[i].second); pa[i][1] += pa[i + 1][1];
  }

  for (int i = 0; i < Q; i++) {
    int query; cin >> query;
    int idx = lower_bound(x, x + N, query) - x;

    int first_sigma = (int)(pa[idx - 1][0] * query) - pax[idx - 1][0];
    int second_sigma = pax[idx][1] - (int)(pa[idx][1] * query);

    //cout << "idx: " << idx << ", pax: " << pax[idx - 1][0] << ", fsig: " << first_sigma << ", ssig: " << second_sigma << endl;

    cout << first_sigma + second_sigma << '\n';
  }
}