[C]백준_11971 : 속도 위반

Alal11·2023년 3월 23일
0
post-thumbnail

출처

https://www.acmicpc.net/problem/11971


문제

말썽꾸러기 연정이는 오늘도 태우의 자동차를 몰래타고 신나게 도로를 달리는 중이다.

도로는 정확히 100km 이고, 연정이는 무조건 도로의 끝까지 달려야한다.

도로의 각 구간에는 제한속도를 지정해 두었으나 쿨한 연정이는 속도 위반에는 개의치 않아 (더군다나 자신의 차도 아니므로) 자신이 원하는 속도로 달린다.

도로는 N개의 구간으로 나뉘며 각 구간에는 도로 길이와 해당 도로의 제한속도가 주어진다.

도로 N개의 총 합은 100km 이며 각 구간별 도로 길이와 제한 속도는 모두 양의 정수이다. 예를 들어, N이 3이고 (40, 75), (50, 35), (10, 45) 이라면

  • 첫 구간의 도로 길이는 40km, 제한속도는 75km/h
  • 두 번째 구간의 도로 길이는 50km, 제한 속도는 35km/h
  • 세 번째 구간의 도로 길이는 10km, 제한 속도는 45km/h

연정이가 달린 도로 또한 M 개 구간으로 나뉘며 각 구간에는 도로 길이와 연정이가 달린 속도가 주어진다.

M 개의 도로 총 합은 100km 이며 각 구간별 도로 길이와 달린 속도는 모두 양의 정수이다. 예를 들어 M 이 3이고 (40, 76), (20, 30), (40, 40) 이라면

  • 첫 구간에서 연정이가 달린 도로 길이는 40km, 달린 속도는 76km/h
  • 두 번째 구간에서 달린 도로 길이는 20km, 달린 속도는 30km/h
  • 세 번째 구간에서 달린 도로 길이는 40km, 달린 속도는 40km/h

연정이가 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);      // 속도 위반한 최댓값
}

➡️코드 분석

  1. 먼저, 시작 지점에서 x km 떨어진 지점에서의 제한 속도와 연정이의 속도를 담을 배열 limit_speed와 mySpeed를 선언해준다.

  2. n과 m을 입력받고, n만큼 반복하여 각 구간의 길이를 인덱스로 하고, 해당 구간의 제한 속도를 요소 값으로 하여 limit_speed에 넣어준다.

  3. m만큼 반복하여 위 과정과 똑같이 연정이가 달린 각 구간의 길이와 해당 구간에서 달린 속도를 인덱스와 요소 값으로 하여 my_Speed에 넣어준다.

  4. 도로의 길이는 100km 이므로 인덱스 0부터 99까지 반복하여 해당 구간에서 연정이의 속도와 제한 속도의 차의 최댓값을 구하고 출력한다.


➡️end

생각보다 재밌는 문제였다! 거리를 배열의 인덱스로 하고 속도를 요소 값으로 두는 아이디어가 정말 좋다😆

0개의 댓글