Softeer Lv2. GBC

최대공배수 최소공배수 이런 문제인줄 알았는데

이름 낚시였음

구현문제

https://softeer.ai/practice/6270

1. 문제

---

간단 설명

범위와 제한속도가 주어지고

실제 주행거리와 달린 속도가 주어진다

이를 통해 가장 크게 제한 속도를 넘어간 값이 얼마인지 구하는 문제

2. 문제 분석

---

다음과 같이 도로가 있을때

3개의 (50, 50)(40, 40)(10, 30) 가 주어진다면

위의 그림과 같이 속도제한이 붙게된다

이후 실제 주행 거리와 속도 3개

(60, 76)(18, 28)(22, 50) 가주어지면

아래와 같이 기록할 수 있다

이를 0~100m 를 각 1m별로 끊어 이산적으로 생각하면

0m일때는 속도제한은 50km/h, 실제 속도는 76km/h 이므로 26km/h 만큼 과속

1m일때는 속도제한은 50km/h, 실제 속도는 76km/h 이므로 26km/h 만큼 과속

…

51m 일때는 속도제한은 40km/h, 실제 속도는 76km 이므로 36kmh/h 만큼 과속

…

99m 일때는 속도 제한은 30km/h, 실제 속도는 50km/h 이므로 20km/h 만큼 과속

임을 알 수 있다

이를 이용해 문제를 해결한다

필요변수

범위 개수 N, 테스트 구간 개수 M

속도 제한을 저장할 100칸짜리 벡터 limit

실제 운행 속도를 기록할 100칸짜리 벡터 current_speed

최고 기록을 기록할 max_diff

이외에도 계산을 위해 필요한 인덱스와 변수 등

알고리즘

1. 범위 개수와 테스트 구간 개수 N, M을 입력받는다
2. N개만큼 다음을 입력받는다
    2-1. 범위와 속도를 입력받는다
    2-2. K~K+range 만큼의 거리를 제한속도를 기록해둔다
    2-2. K를 range만큼 이동시킨다. <- 인덱스로 사용함
3. k를 0으로 초기화 시키고  M개만큼 다음을 입력받는다
    3-1. 범위와 속도를 입력받는다
    3-2. K~K+range 만큼의 거리를 실제 속도를 기록해둔다
    3-2. K를 range만큼 이동시킨다. <- 인덱스로 사용함
4. 0m부터 100m까지 제한속도와 실제속도를 비교하여 가장 큰 차이값을 찾아 출력한다 

3. 소스코드

---

#include <iostream>
#include <vector>

using namespace std;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int N, M;
	vector<int> limit;
	vector<int> current_speed;

	cin >> N >> M;
	int k = 0;
	for (int i = 0; i < N; i++) {
		int range, speed;
		cin >> range >> speed;

		int next_range = k + range;
		for (int j = k; j < next_range; j++) {
			limit.push_back(speed);
			k++;
		}
	}
	k = 0;
	for (int i = 0; i < M; i++) {
		int range, speed;
		cin >> range >> speed;

		int next_range = k + range;
		for (int j = k; j < next_range; j++) {
			current_speed.push_back(speed);
			k++;
		}
	}
	int max_diff = 0;
	for (int i = 0; i < 100; i++) {
		int diff = current_speed[i] - limit[i];
		if (max_diff < diff) {
			max_diff = diff;
		}
	}

	cout << max_diff;

	return 0;
}