[BOJ] 랜덤 마라톤 (No. 14173, 13411, 31797, 20126, 24495, 30446, 21868, 1916)

14173

문제

문제
농부 존(Farmer John)은 자신의 농장의 지형을 단순화하려고 한다. 이전에 그의 소들은 두 개의 직사각형 울타리로 둘러싸인 목초지에서 풀을 뜯었다. 농부 존은 이 두 울타리를 대체하여, 두 울타리가 차지했던 모든 영역을 포함하는 최소 크기의 정사각형 울타리로 교체하려고 한다.
농부 존이 새로 설치할 정사각형 울타리의 최소 면적을 계산하는 데 도움을 주어라. 이 정사각형 울타리는 적절히 배치되면 이전 두 직사각형 울타리가 둘러싸고 있던 모든 영역을 포함할 수 있어야 한다. 정사각형 울타리의 변은 x축과 y축에 평행해야 한다.

입력
입력 파일의 첫 번째 줄에는 첫 번째 직사각형 목초지를 나타내는 네 개의 정수 x1, y1, x2, y2가 공백으로 구분되어 주어진다. 각각의 값은 (0 <= x1, y1, x2, y2 <= 10) 범위에 속한다.  
첫 번째 목초지의 왼쪽 아래 꼭짓점은 (x1, y1), 오른쪽 위 꼭짓점은 (x2, y2)에 위치하며,(x2 > x1이고 y2 > y1이다.
두 번째 줄도 같은 형식으로 네 개의 정수가 주어지며, 두 번째 직사각형 목초지를 나타낸다. 이 목초지는 첫 번째 목초지와 겹치거나 접하지 않는다.

출력
입력된 두 직사각형 목초지를 모두 포함하는 정사각형 울타리의 최소 면적을 한 줄로 출력한다.

예제 입력 1
6 6 8 8
1 8 4 9
예제 출력 1
49

힌트
위 예제에서 첫 번째 직사각형은 꼭짓점 (6,6)과 (8,8)을 가진다. 두 번째 직사각형은 꼭짓점 (1,8)과 (4,9)에 위치한다.  
한 변의 길이가 7인 정사각형 울타리(꼭짓점 (1,6)과 (8,13))를 설치하면 두 직사각형이 포함된다. 한 변의 길이가 6인 정사각형으로는 포함할 수 없기 때문에 이것이 최선의 경우이다.  
참고로, 한 변의 길이가 7인 정사각형을 수직으로 약간 이동하여도 유효한 배치가 될 수 있다.

풀이

꼭짓점의 x 좌표끼리의 최대 차와 y좌표끼리의 최대 차를 비교한 이후에 가장 큰 값을 제곱하면 풀리는 문제.

#include <bits/stdc++.h>

using namespace std;

int field[2][4];
int ans;

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

  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> field[j][i];
    }
  }

  sort(field[0], field[0] + 4);
  sort(field[1], field[1] + 4);

  cout << pow(max(field[0][3] - field[0][0], field[1][3] - field[1][0]), 2);
}

 

13411

문제

하늘에서 정의가 빗발친다!
 
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	2204	849	697	40.976%

문제
오버워치에 빠진지도 어언 6개월. 50점에서 시작한 경쟁전 점수는 어느새 35점까지 내려와 버렸다. 알고리즘을 공부하느라 게임 실력이 떨어졌다고 생각한 규현이는 오버워치 경쟁전 점수를 올리기 위해 새로운 캐릭터 파라를 선택하여 연습을 시작하였다. 포화 개시! 처음 사격을 시작한 규현이의 파라는 형편없는 명중률을 보여주었지만, 곧이어 모든 미사일이 적의 로봇을 명중시키는 놀라운 결과를 얻어내었다. 파라를 계속 연습하던 규현이는 파라가 미사일을 쏘는 순간, 알고리즘 능력이 발휘되어 그 장면이 머릿속에서 좌표평면으로 그려졌다. 

규현이의 파라는 (0,0) 의 위치에 있으며, 궁극기를 사용할 시 미사일을 적의 모든 로봇에게 동시에 직선으로 발사하여 맞춘다. 미사일의 날아가는 속도가 미사일마다 모두 달라 더 멀리 있는 적을 가까이 있는 적보다 더 빨리 맞출 수도 있게 된다. 알고리즘의 늪에서 빠져나올 수 없었던 걸까? 규현이는 적이 미사일에 격추되는 순서를 구하는 프로그램을 만들려고 한다. 규현이를 도와 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. N은 100,000보다 작거나 같은 수이다.

둘째 줄부터 총 N개의 줄에는 Xi, Yi, Vi 가 주어진다. 이는 i번째 로봇의 x, y 좌표와 미사일이 이 로봇을 향해 날아가는 속도를 의미한다. (|Xi, Yi|≤10,000, 0＜Vi ≤1,000)

입력값이 주어지는 대로 로봇이 나타난 순서를 의미하며, 맨 처음 나타난 로봇부터 1, 2, 3, ..., N번째 로봇으로 지정한다. x좌표와 y좌표가 같은 곳에 로봇이 2개 이상 존재하는 경우는 없다.

출력
로봇이 격추되는 순서를 한 줄에 하나씩 출력한다. 동시에 격추되는 경우 더 작은 로봇의 번호를 먼저 출력한다.

예제 입력 1 
4
3 3 1
-3 2 3
-3 -3 1
4 -4 4
예제 출력 1 
2
4
1
3

풀이

걸리는 시간과 번호를 벡터에 집어넣은 다음에 정렬하면 풀리는 문제

#include <bits/stdc++.h>

using namespace std;

vector<pair<long double, int>> para;
int n;

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

  cin >> n;
  para.resize(n);

  for (int i = 0; i < n; i++) {
    int x, y, v;
    cin >> x >> y >> v;

    para[i] = {sqrt(x * x + y * y) / v, i + 1};
  }

  sort(para.begin(), para.end());

  for (int i = 0; i < n; i++) {
    cout << para[i].second << '\n';
  }
}

 

31797

문제

아~파트 아파트
 
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	1024 MB	2343	563	469	25.869%

문제
부산대학교 정보컴퓨터공학부는 매년 봄 MT를 떠난다. 봄 MT에 간 산지니는 아파트라는 술게임을 배웠다.
게임을 시작한 사람이 아파트의 층수 N을 정한다.
게임의 모든 참가자는 자신의 두 손을 다른 사람과 겹치지 않는 높이로 뻗어 모든 참가자의 두 손이 서로 쌓이도록 한다.
가장 아래에 있는 손을 빼 쌓여있는 손 가장 위에 쌓는다.
3.의 과정을 N번 반복한다. j번째로 쌓은 손이 j층이 된다.
N층을 쌓는 참가자가 술을 마시고 게임이 종료된다.
새내기인 산지니는 누가 술을 마시게 될 지 궁금해졌다. 산지니를 위해 누가 술을 마시게 될 지 구해주자.

입력
첫 번째 줄에 아파트의 층수 N, 참가자의 수 M이 공백으로 구분되어 주어진다. (1 <= N, M <= 1,000) 
두 번째 줄부터 M+1번째 줄까지 i번 참가자의 두 손의 높이 H_{1,i}, H_{2,i}가 공백으로 구분되어 주어진다. (1 <= H_{1,i}, H_{2, i} <= 10,000)$
어떤 두 손도 같은 높이인 경우는 주어지지 않는다. 모든 입력은 정수이다.

출력
술을 마시게 될 사람의 번호를 출력한다.

예제 입력 1 
5 3
1 6
3 4
2 5
예제 출력 1 
3

풀이

사람들의 손 높이와 사람 번호를 벡터에 저장한 다음에 층수에 해당하는 사람의 번호를 출력해서 해결하였다.

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<pair<int, int>> hand;

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

  cin >> n >> m;

  hand.resize(m * 2);

  for (int i = 1; i <= m; i++) {
    int temp;
    cin >> temp;

    hand[(i - 1) * 2] = {temp, i};

    cin >> temp;
    hand[(i - 1) * 2 + 1] = {temp, i};
  }

  sort(hand.begin(), hand.end());

  cout << hand[(n - 1) % (m * 2)].second << '\n';
}

 

20126

문제

교수님의 기말고사
 
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	1024 MB	1173	349	290	31.625%

문제
안형찬 교수님은 알고리즘 분석 기말고사를 준비하려고 한다.

알고리즘 기말고사는 총 M분 동안 쉬는 시간 없이 볼 예정이며, 인원이 너무 많아서 공학관 C040호에서 말고 다른 강의실에서 시험을 치를 수 없게 되었다.

공학관 C040호는 0분부터 S분까지 사용 가능하다. S는 무조건 M 이상이기 때문에 안 교수님은 별문제 없이 시험을 치를 것으로 생각하였다. 그러나 공학과 C040호에는 다른 시험도 예정되어 있어서 겹치지 않는 시간을 잡아야 한다.

각 시험은 xi분에 시작해서 yi분 동안 진행하며 서로 겹치지 않는다. 한 시험이 끝난 직후 다음 시험이 있는 경우도 겹치지 않는 것으로 판단한다. 즉, xi + yi ≤ xj 일 때 i 시험과 j 시험은 서로 겹치지 않는다.

안형찬 교수님이 시험을 언제 치를 수 있는지 구해보자.

입력
다음과 같이 입력이 주어진다.

N M S
x1 y1
. . .
xN yN
출력
교수님이 시험을 시작할 수 있는 시각을 출력하여라. 시작 가능한 시각이 여러 개 있으면 그중 가장 앞선 시각을 출력한다. 시험을 치룰 수 없다면 -1을 출력하여라.

제한
1 ≤ N ≤ 100,000.
1 ≤ M ≤ S ≤ 1,000,000,000. 
0 ≤ xi < xi + yi ≤ S.
입력에 주어진 수들은 전부 정수다.

예제 입력 1 
2 3 5
0 1
4 1
예제 출력 1 
1

예제 입력 2 
2 3 5
0 2
4 1
예제 출력 2 
-1

풀이

각 시험의 정보를 벡터에 넣어서 저장한 다음 정렬한다.

이후 모든 시험들을 앞 뒤로 확인하여 ~M~ 이상으로 비어있는 시간을 확인하여 해결하였다.

 

첫 시험 이전, 마지막 시험 이후에도 비어있는 시간이 있을 수 있기에 이를 확인하기 위해 0과 S에 시작하고 0만큼 지속되는 시험을 각각 벡터에 추가하였다.

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> exam;
int n, m, s;

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

  cin >> n >> m >> s;

  exam.push_back({0, 0});
  exam.push_back({s, 0});

  for (int i = 0; i < n; i++) {
    int b, t;
    cin >> b >> t;
    exam.push_back({b, t});
  }

  sort(exam.begin(), exam.end());

  for (int i = 0; i < n + 1; i++) {
    if (exam[i + 1].first - (exam[i].first + exam[i].second) >= m) {
      cout << exam[i].first + exam[i].second;
      return 0;
    }
  }

  cout << -1;
  return 0;
}

 

21868

문제

\[
\lim_{x \to x_0} f(x) = L : \text{For a given } \epsilon > 0, \text{ there exists a } \delta > 0 \text{ such that } 0 < |x - x_0| < \delta, \\
\text{then } |f(x) - L| < \epsilon
\]

미적분학 입문하기
 
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	1024 MB	563	183	162	37.500%

문제
이공계 대학생들은 대학교에 입학하면 반드시 입실론-델타 논법을 배운다. 위의 식은 입실론-델타 논법을 이용한 극한의 정의다.

21학번 신입생들이 수강하고 있는 연세대학교 공학수학 I의 2차 퀴즈가 저번 주에 있었다. 국렬이는 연세대학교 신입생들에게 극한의 정의에 관한 내용을 되새겨주기 위해서 이 문제를 출제했다.

문제는 간단하다. 양수 
epsilon과 정수 x_0, 그리고 일차 이하의 다항함수 f(x)가 주어졌을 때,  
lim_{x \to x_0} f(x)의 값인 L을 찾고, |f(x) - L| < epsilon을 만족하는 양수 delta의 최댓값을 구해보자.

입력
첫 번째 줄에는 양수 epsilon을 분수로 표현했을 때의 분자와 분모가 공백으로 구분되어 주어진다. 각 분자와 분모는 1 이상 10,000 이하의 자연수다.
두 번째 줄에는 일차 이하의 다항함수 f(x)의 x의 계수와 상수가 공백으로 구분되어 주어진다. x의 계수와 상수는 -10,000 이상 10,000 이하의 정수다.
마지막 줄에는 정수 x_0이 주어진다. (-10,000 <= x_0 <= 10,000)

출력
첫 번째 줄에 극한값 L을 출력한다.
두 번째 줄에 양수 \delta의 최댓값을 분수로 표현했을 때의 분자와 분모를 공백으로 구분해서 출력한다. 해당 분수가 기약분수일 필요는 없으나, 분자와 분모는 10^8 이하의 자연수여야 한다. 만약에 양수 delta의 최댓값이 존재하지 않거나 최댓값을 분수로 표현했을 때의 분자, 분모를 10^8 이하의 자연수로 표현할 수 없다면 0 0을 출력한다.
답이 여러 가지 존재하는 경우, 그 중 하나만 출력한다.

예제 입력 1 
1 1
1 1
1
예제 출력 1 
2
1 1

풀이

첫번째 줄에는 

$ {a_1} * {x_0} + {a_1}$을 출력하면 된다.

델타의 최댓값은

\[
\frac{\epsilon}{|a_1|}
\]

이므로 a_1이 0이 아니라면 델타의 최댓값을 출력하고, 그렇지 않다면 0 0을 출력하면 된다. 

#include <bits/stdc++.h>
using namespace std;

int en, ed, a1, a0, x;

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

  cin >> en >> ed >> a1 >> a0 >> x;

  cout << a1 * x + a0 << '\n';

  if (a1 == 0) {
    cout << "0 0\n";
    return 0;
  }

  cout << en << " " << ed * abs(a1) << '\n';
}

 

1916

문제

최소비용 구하기 성공
 
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초	128 MB	106930	35582	23568	32.629%

문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

예제 입력 1 
5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력 1 
4

풀이

다익스트라로 시작점부터 도착점 까지의 최단 거리를 구하면 된다.

단방향 버스라는 점, 한 지점에서 다른 지점으로 가는 버스가 여러개가 있을 수 있다는 점을 고려해야 한다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<pair<int, int>> city[1001];

vector<long long> dijkstra(int start) {
  vector<long long> dist(n + 1, LLONG_MAX);
  dist[start] = 0;
  priority_queue<pair<int, int>> pq;
  pq.push({0, start});

  while (!pq.empty()) {
    int cost = -pq.top().first;
    int cur = pq.top().second;
    pq.pop();

    if (dist[cur] < cost) continue;

    for (int i = 0; i < city[cur].size(); i++) {
      int next = city[cur][i].first;
      int nextCost = city[cur][i].second + cost;

      if (dist[next] > nextCost) {
        dist[next] = nextCost;
        pq.push({-nextCost, next});
      }
    }
  }

  return dist;
}

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

  cin >> n >> m;

  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    city[a].push_back({b, c});
  }

  int s, e;
  cin >> s >> e;

  vector<long long> dist = dijkstra(s);

  cout << dist[e] << '\n';
}