[백준 10471] 공간을 만들어 봅시다 (C#, C++) - soo:bak

문제 링크

10471번 - 공간을 만들어 봅시다

설명

주어진 전체 폭과 설치 가능한 파티션 위치를 기준으로, 만들 수 있는 공간의 폭을 모두 구하는 문제입니다.

오피스는 가로로 긴 직사각형 구조이며, 일부 위치에 세로 방향의 파티션을 선택적으로 설치할 수 있습니다.

이 때, 파티션을 반드시 설치할 필요는 없으며, 여러 개를 조합해 다양한 크기의 공간을 만들 수 있습니다.

가능한 모든 거리 조합을 계산하여 중복 없이 오름차순으로 출력합니다.

접근법

• 전체 폭 W와 설치 가능한 파티션 개수 P를 입력받습니다.
• 파티션 위치 리스트 앞뒤에 0과 W를 추가하여 벽을 포함합니다.
• 이 리스트에서 가능한 두 위치 쌍을 모두 선택하여, 거리(공간의 폭)를 계산합니다.
• 가능한 모든 거리값 중에서 중복 없이 한 번만 등장하는 값들을 골라, 오름차순으로 출력합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var input = Console.ReadLine().Split();
    int w = int.Parse(input[0]);
    int p = int.Parse(input[1]);

    var arr = new int[p + 2];
    var used = new bool[w + 1];

    arr[0] = 0;
    var parts = Console.ReadLine().Split();
    for (int i = 1; i <= p; i++)
      arr[i] = int.Parse(parts[i - 1]);
    arr[p + 1] = w;

    for (int i = 0; i <= p + 1; i++) {
      for (int j = i + 1; j <= p + 1; j++) {
        used[arr[j] - arr[i]] = true;
      }
    }

    for (int i = 1; i <= w; i++) {
      if (used[i]) Console.Write(i + " ");
    }
    Console.WriteLine();
  }
}

C++

#include <bits/stdc++.h>

using namespace std;
typedef vector<int> vi;

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

  int n, p; cin >> n >> p;
  vi arr(p + 3), used(n + 1);
  arr[1] = 0;
  for (int i = 2; i <= p + 1; i++)
    cin >> arr[i];

  arr[p + 2] = n;

  for (int i = 1; i <= p + 2; i++) {
    for (int j = i + 1; j <= p + 2; j++)
      used[arr[j] - arr[i]] = 1;
  }

  for (int i = 1; i <= n; i++) {
    if (used[i]) cout << i << " ";
  }
  cout << "\n";

  return 0;
}