중등부 2교시 풀이

* 대회에서 만점을 받은 코드이지만, 테스트 케이스의 문제로 정확한 풀이가 아닐 수 있습니다.
* 모든 정보는 제가 복기한 것이니, 맞지 않는 정보가 있을 수 있습니다.
* 문제의 저작권은 한국정보과학회와 한국정보올림피아드에 있습니다.
* 설명이 부족해서 죄송합니다.
* 2번의 예제 2, 3은 직접 만든 테스트 케이스입니다.

1번: 양팔저울
– 문제
그릇과 추 t개가 있다. 그릇의 무게는 0이며, 추 t개의 무게는 주어진다. 그릇에는 물을 담을 수 있으며, 제한은 없다. 그릇과 추들은 양팔저울의 양쪽에 놓을 수 있다. 추 t개와 양팔저울을 한 번만 이용하여 1 <= n <= s인 정수 n에 대하여 측정할 수 없는 무게 ng의 개수를 출력하라. g는 무게의 단위이고, s는 모든 추의 무게의 합이다.
– 입력
1 <= t <= 13인 추의 개수 t가 첫째 줄에 입력된다.
1 <= g_i <= 20000인 정수인 i번째 추의 무게 g_i가 둘째 줄부터 t + 1째 줄까지 한 줄에 하나씩 입력된다.
– 출력
답을 첫 번째 줄에 출력한다.
– 예제 입력
3
1 5 7
– 예제 출력
2

– 풀이 (c++)
그릇을 왼쪽에 놓고 추 n개를 오른쪽에 놓았을 때, 사용하지 않은 추를 오른쪽의 무게에 더하거나, 빼거나, 아무것도 하지 않아도 된다는 것을 생각하면 됩니다. 0에서부터 DFS/BFS 탐색할 수 있습니다. 아래 코드는 DFS를 사용하였습니다.
/// 예시 코드
#include <cstdio>

int t, g[14], s;
bool arr[260001];

void dfs(int sum, int index) {
   if (index >= t) {
       if (sum < 0) return;
       arr[sum] = true;
   } else {
       dfs(sum + g[index], index + 1);
       dfs(sum, index + 1);
       dfs(sum – g[index], index + 1);
   }
}

int main(int argc, char *argv[]) {
   scanf(“%d”, &t);
   for (int i = 0; i < t; i++) scanf(“%d”, g + i), s += g[i];
   dfs(0, 0);
   int res = 0;
   for (int i = 1; i < s; i++) res += !arr[i];
   printf(“%d”, res);
   return 0;
}

2번: 단순직각다각형
– 문제
다각형의 모든 선분들의 쌍이 연속되는 꼭짓점에서 만나는 경우를 제외하고 만나는 경우가 없으면, 그 다각형을 “단순다각형”이라고 한다. 다각형의 모든 선분들이 x축 또는 y축에 대하여 평행하면 그 다각형을 “직각다각형”이라고 한다. “단순다각형”이고 “직각다각형”인 다각형을 “단순직각다각형”이라고 한다. “단순직각다각형”의 p개의 꼭짓점들이 주어지며, 주어지는 순서대로 꼭짓점들을 이어서 이 다각형을 만들 수 있다. 임의의 수직선과 이 다각형이 만나는 최대의 점의 개수를 h라고 하고, 임의의 수평선과 이 다각형이 만나는 최대의 점의 개수를 v라고 할 때, max(h, v)를 출력하여라. 단, 수직선과 수평선이 다각형과 무한히 많은 점에서 만나는 경우는 제외한다.
– 입력
4 <= p <= 1000인 꼭짓점의 개수 p이 첫째 줄에 입력된다.
-500000 <= x_i, y_i <= 500000인 정수인 i번째 꼭짓점의 좌표 x_i, y_i가 둘째 줄부터 p + 1째 줄까지 입력된다.
– 출력
답을 첫 번째 줄에 출력한다.
– 예제 입력 1
4
-1 -1
-1 1
1 1
1 -1
– 예제 출력 1
2
– 예제 입력 2
16
16
-20 -5
-10 -5
-10 0
0 0
0 -2
2 -2
2 5
4 5
4 -1
8 -1
8 0
7 0
7 10
-1 10
-1 3
-20 3
– 예제 출력 2
6
– 예제 입력 3
8
-2 -1
2 -1
2 0
1 0
1 -1
-1 -1
-1 0
-2 0
– 예제 출력 3
2
– 풀이 (c++)
1) x축과 y축에 해당하는 배열을 만들고, x = i일 때 겹치는 선분 개수를 x[i + 500000]개, y = i일 때 겹치는 선분 개수를 y[i + 500000]개라고 합니다. 모든 선분마다 x와 y를 업데이트하고, 마지막에 수직선 또는 수평선과 이 다각형이 겹치는 최대 횟수를 찾습니다. 이 방법으로는 시간 초과를 받으며, 부분 점수를 받게 됩니다.
2) x축과 y축에 해당하는 배열을 만들고, x = i일 때 겹치는 선분 개수의 변화량을 x[i + 500000], y = i일 때 겹치는 선분 개수의 변화량을 y[i + 500000]라고 하면, 문제가 해결 가능합니다.
/// 예시 코드
#include <cstdio>
#include <algorithm>
using namespace std;

int p, simulate[2][1000005];
pair<int, int> pos, old, first;

void f() {
   bool w = false;
   if (pos.first == old.first) w = true;
   if (w) {
       simulate[0][min(pos.second, old.second) + 500000]++;
       simulate[0][max(pos.second, old.second) + 500000]–;
   } else {
       simulate[1][min(pos.first, old.first) + 500000]++;
       simulate[1][max(pos.first, old.first) + 500000]–;
   }
}

int main(int argc, char *argv[]) {
   scanf(“%d”, &p);
   for (int i = 0; i < p; i++) {
       scanf(“%d%d”, &pos.first, &pos.second);
       if (!i) {
           old = first = pos;
           continue;
       }
       f();
       old = pos;
   } pos = first; f();

   int res = 0, r0 = 0, r1 = 0;
   for (int i = 0; i <= 1000000; i++) {
       r0 += simulate[0][i];
       res = max(res, r0);
       r1 += simulate[1][i];
       res = max(res, r1);
   }
   printf(“%d”, res);
}