홈 [C++] softeer level2 GBC
포스트
취소

[C++] softeer level2 GBC

게시 2023/07/30
By dapin
11 분읽는 시간

Table of Contents

문제

지정된 구간에서의 제한 속도와 시험 운행 기록이 주어진다. 운행 구간 중 제한 속도를 가장 많이 초과했을 때 제한 속도와 운행 속도의 차이를 구하라.

나는 구현 문제가 그렇게 귀찮더라

계획

일단 사람 머리로 한번 풀어보자. 문제 예제 그대로 하면 첫 구간은 50m지만 시험 운행을 할 때는 한번에 60m를 달렸으니 첫 번째 구간과 두 번째 구간이 섞여있다. 여기서 첫 번째 구간은 26 초과, 두 번째 구간은 36 초과했다. 이후는 이 이상 초과한 구간이 없으므로 답은 36을 출력해야 맞다.

구간을 비교할 때는 주어진 구간과 시험 운행한 구간 중 작은 것을 기준으로 큰 것을 잘랐다, 라기 보다는 지정 구간은 굳이 자를 필요가 없고 운행 구간만 자르면 될 것 같지 않나? 덧뺄셈으로 뭔가 해결이 될 것 같은데.

일단 생각나는 방법은 두 가지.

  1. 시뮬레이션 방식으로 1m씩 전진하면서 매번 속도 비교하고 최대 위반 속도 구하기: 불필요한 계산이 너무 많기 때문에 쓰면 안 되는 방법이다. 라고 아래 방법 틀리고 풀이 찾아보기 전까지 그렇게 생각했었다..
  2. 시험 운행 구간 기준으로 구간마다 나아가되, 지정 구간과 비교하여 겹치는 구간에 대해 속도 위반 계산하기: 이 요약된 서술 안에서 세부 과정을 얼마나 간단하게 쓰느냐에 따라 다르겠지만 일단은 괜찮아 보임.

무엇을 저장해야 하나?

  • 지정 구간과 속도: 먼저 입력되기 때문에 전부 저장하고 있어야 함.
  • 운행 구간과 속도: 나중에 입력되기 때문에 입력받는 것과 동시에 계산한다면 전부 저장할 필요는 없음. 근데 그거 뭐 얼마나 한다고 int 4개 줄여서 무슨 용량을 줄이겠다고 그러나 싶긴 한데 이걸 1000m로 확장한다 더 크게 한다 생각하면 유효할 수는 있을듯
  • 최고 위반 속도 차: 이게 답이니까 알아야지
  • 현재 운행 중인 구간이 몇 번째인지 / 직전까지 운행한 구간이 어디였는지: 이 부분이 아직 좀 불확실함. 이걸 어덯게 다뤄야 내가 생각한 흐름대로 가나?

알고리즘 써보기

  1. 지정 구간과 속도를 입력받는다 → 구간은 누적합으로 저장한다.
  2. 운행 구간을 입력 받으면서 다음을 수행한다.
    1. 누적 주행 구간을 계산하고, 이번 구간에서 지나간 구간을 찾는다. → 이번 주행 구간의 누적 시작점과 누적 도착점을 기록해서, 그 사이에 있는 지정 구간만 찾아낸다.
    2. 해당 지정 구간 내에서 지정 속도와 운행 속도의 차를 계산하고 최댓값 갱신.
    3. 운행을 완료할 때까지 위 과정 반복

다시 계획

  1. 지정 구간과 속도를 입력받으면서, 1m 단위로 제한 속도를 배열에 저장한다.
  2. 운행 구간을 누적합으로 입력받으면서 다음을 수행한다.
    1. 현재 구간 내에서 1m 단위로 제한 속도 위반 차이 최댓값을 갱신한다.
    2. 운행을 완료할 때까지 반복

아니.. 그래도 이것보다 더 적은 계산으로 풀 수 있는 방법이 있는 게 아냐? 찾아보니까 다르게 쓴 사람이 있긴 했는데, 풀이도 아무 설명도 없이 딱 코드만 올려놔서 좀 알아먹기는 어려웠다. 다른 문제 더 풀다가 나중에 다시 보게 되면 딱 이해가 되는 순간이 있겠지. → 이렇게 써놓고 직접 고쳤음

풀이

이게 10m 주행하고 20m 더 주행했다 하면 0m ~ 10m까지, 11m ~ 20m까지 구간을 나눠야 하는데, 풀이를 고치니까 저 1 차이가 걸리더라. 생각하지 못한 부분이었음. 그리고 틀린 풀이도 반례 찾아보니까 그 1 차이가 문제였던 것 같다. 저런.

하지만 내가 또 이런 일 생기면 승부욕 돈다고 시간낭비 좀 하는 사람이지. 시간을 더 들여서 원래 내 풀이도 다 고쳤다. 결국 이분 탐색은 뺐지만.

오답

특정 값 이상이면서 그 다음 값 미만인 인덱스를 찾는 이분 탐색을 구현해보려고 했는데, 채점이 틀린 걸 봐선 뭔가 틀린 구석이 있는 거겠지?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <iostream>
#include <vector>
using namespace std;

int find_section(vector<pair<int, int>>& rule, int start, int before = 0) {
  int left = before, right = rule.size() - 1, mid = right / 2;
  while (left < right) {
    if (start >= rule[mid].first) {
      left = mid;
      mid = (left + right) / 2;
      if (right - left <= 1)
        return left;
    }
    if (start < rule[mid].first) {
      right = mid;
      mid = (left + right) / 2;
      if (right - left <= 1)
        return right;
    }
  }
  return 0;
}

int main()
{
  // 빠른 입출력
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  int n, m, temp;
  int idx = 0;
  vector<pair<int, int>> rule; // 지정 구간
  pair<int, int> current; // 현재 주행 누적 구간
  int max_speeding = 0; // 속도위반 최댓값

  cin >> n >> m;
  cin >> current.first >> current.second;
  rule.emplace_back(current.first, current.second); // 구간, 속도

  for (int i = 1; i < n; i++) {
    cin >> current.first >> current.second;
    rule.emplace_back(rule[i - 1].first + current.first, current.second);
  }

  current.first = 0;
  for (int i = 0; i < m; i++) {
    cin >> temp >> current.second;
    temp += current.first;
    idx = find_section(rule, current.first + 1, idx);
    while (idx < rule.size()) {
      max_speeding = (current.second - rule[idx].second > max_speeding ? current.second - rule[idx].second : max_speeding);
      if (temp <= rule[idx].first)
        break;
      idx++;
    }
    current.first = temp;
  }

  cout << max_speeding << "\n";
  return 0;
}

정답 - 전구간 탐색

이 방법은 마지막 방법이라고 생각했는데 마지막 방법이 아니게 될 줄이야.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  // 빠른 입출력
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  int n, m, temp = 0;
  vector<int> rule = vector<int>(101); // 지정 구간
  pair<int, int> current; // 현재 주행 누적 구간
  int max_speeding = 0; // 속도위반 최댓값

  cin >> n >> m;
  current.first = 0;

  for (int i = 0; i < n; i++) {
    cin >> temp >> current.second;
    temp += current.first;
    for (int j = current.first + 1; j <= temp; j++)
      rule[j] = current.second;
    current.first = temp;
  }

  current.first = 0;
  for (int i = 0; i < m; i++) {
    cin >> temp >> current.second;
    temp += current.first;
    for (int j = current.first + 1; j <= temp; j++) {
      if (current.second - rule[j] > max_speeding)
        max_speeding = current.second - rule[j];
    }
    current.first = temp;
  }

  cout << max_speeding << "\n";
  return 0;
}

정답 - 동시 진행 탐색

마음에 들어. 나는 이렇게 계산하고 싶었단 말야. 필요한 만큼만 저장하고 필요한 만큼만 비교하기.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  // 빠른 입출력
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  int n, m, temp;
  int idx = 0;
  vector<pair<int, int>> rule; // 지정 구간
  pair<int, int> current; // 현재 주행 누적 구간
  int max_speeding = 0; // 속도위반 최댓값

  cin >> n >> m;
  cin >> current.first >> current.second;
  rule.emplace_back(current.first, current.second); // 구간, 속도

  for (int i = 1; i < n; i++) {
    cin >> current.first >> current.second;
    rule.emplace_back(rule[i - 1].first + current.first, current.second);
  }

  current.first = 0;
  for (int i = 0; i < m; i++) {
    cin >> temp >> current.second;
    temp += current.first;
    if (current.first >= rule[idx].first)
      idx++;
    while (idx < rule.size()) {
      max_speeding = (current.second - rule[idx].second > max_speeding ? current.second - rule[idx].second : max_speeding);
      if (temp <= rule[idx].first)
        break;
      idx++;
    }
    current.first = temp;
  }

  cout << max_speeding << "\n";
  return 0;
}
IT, 문제풀이
지식 IT 문제풀이 softeer
이 기사는 저작권자의 CC BY-NC-ND 4.0 라이센스를 따릅니다.
최근 업데이트