https://www.acmicpc.net/problem/11971
말썽꾸러기 연정이는 오늘도 태우의 자동차를 몰래타고 신나게 도로를 달리는 중이다.
도로는 정확히 100km 이고, 연정이는 무조건 도로의 끝까지 달려야한다.
도로의 각 구간에는 제한속도를 지정해 두었으나 쿨한 연정이는 속도 위반에는 개의치 않아 (더군다나 자신의 차도 아니므로) 자신이 원하는 속도로 달린다.
도로는 N개의 구간으로 나뉘며 각 구간에는 도로 길이와 해당 도로의 제한속도가 주어진다.
도로 N개의 총 합은 100km 이며 각 구간별 도로 길이와 제한 속도는 모두 양의 정수이다. 예를 들어, N이 3이고 (40, 75), (50, 35), (10, 45) 이라면
연정이가 달린 도로 또한 M 개 구간으로 나뉘며 각 구간에는 도로 길이와 연정이가 달린 속도가 주어진다.
M 개의 도로 총 합은 100km 이며 각 구간별 도로 길이와 달린 속도는 모두 양의 정수이다. 예를 들어 M 이 3이고 (40, 76), (20, 30), (40, 40) 이라면
연정이가 100km 도로를 달리는 동안 속도를 위반한 최댓값을 구하시오.
첫 줄에 N과 M이 주어진다. 그 다음 줄부터 N개의 줄은 각 구간의 길이 및 해당 구간에서의 제한 속도가 주어지며, 다음 M개의 줄은 연정이가 달린 각 구간의 길이와 해당 구간에서 달린 속도가 주어진다.
연정이가 도로를 달리는 동안 속도 위반한 최댓값을 출력하시오. 단, 속도 위반을 하지 않았다면 0을 출력하시오.
예를 들어 도로가 3구역 [(40km, 75km/h), (50km, 35km/h), (10km, 45km/h)] 이고. 연정이가 달린 3구역 [(40km, 76km/h), (20km, 30km/h), (40km, 40km/h)] 이라면, 처음 0 ~ 40km 영역에서 1km/h 만큼 위반했으나 60km ~ 90km 사이에서 5km/h 만큼 위반했기에 연정이가 위반한 최대 값은 5 이다.
해당 구간에서 연정이의 속도와 제한 속도의 차이를 구하고 그 최댓값을 출력하면 되는 문제이다.
#include <stdio.h>
int main()
{
int n, m;
// limit_speed[x]는 시작 지점에서 x km 떨어진 지점에서의 제한 속도
// mySpeed[x]는 시작 지점에서 x km 떨어진 지점에서의 연정이의 속도
int limit_speed[100] = { 0 };
int mySpeed[100] = { 0 };
int lastIdx = 0;
int len, speed;
int max = 0;
scanf("%d %d", &n, &m); // n개의 구간, 연정이가 달린 m개의 구간
// 각 구간의 길이와 제한 속도
for (int i = 0; i < n; i++) // n번 반복
{
scanf("%d %d", &len, &speed); // 각 구간의 길이와 제한속도 입력
for (int j = lastIdx; j < lastIdx + len; j++)
limit_speed[j] = speed;
lastIdx += len;
}
lastIdx = 0;
// 연정이가 달린 각 구간의 길이와 해당 구간에서 달린 속도
for (int i = 0; i < m; i++)
{
scanf("%d %d", &len, &speed);
for (int j = lastIdx; j < lastIdx + len; j++)
mySpeed[j] = speed;
lastIdx += len;
}
// 1 ~ 100까지 반복문을 돌며, 두 속도를 비교하여 가장 큰 값 출력
for (int i = 0; i < 100; i++)
{
int diff = mySpeed[i] - limit_speed[i];
if (diff > max)
max = diff;
}
printf("%d", max); // 속도 위반한 최댓값
}
먼저, 시작 지점에서 x km 떨어진 지점에서의 제한 속도와 연정이의 속도를 담을 배열 limit_speed와 mySpeed를 선언해준다.
n과 m을 입력받고, n만큼 반복하여 각 구간의 길이를 인덱스로 하고, 해당 구간의 제한 속도를 요소 값으로 하여 limit_speed에 넣어준다.
m만큼 반복하여 위 과정과 똑같이 연정이가 달린 각 구간의 길이와 해당 구간에서 달린 속도를 인덱스와 요소 값으로 하여 my_Speed에 넣어준다.
도로의 길이는 100km 이므로 인덱스 0부터 99까지 반복하여 해당 구간에서 연정이의 속도와 제한 속도의 차의 최댓값을 구하고 출력한다.
생각보다 재밌는 문제였다! 거리를 배열의 인덱스로 하고 속도를 요소 값으로 두는 아이디어가 정말 좋다😆