사다리

사다리

문제

 

여러 층으로 이루어진 직사각형 모양의 건물이 있다. 아래 그림 1은 5개의 층으로 이루어진 직사각형 건물의 예이다. 

각 층에는 하나의 막대기가 있는데, 각 막대기의 길이는 서로 다를 수 있다. 

그리고 막대기들은 시간 0에서 시작해서 동시에 왼쪽에서 오른쪽으로 혹은 오른쪽에서 왼쪽으로 움직인다. 

시간은 정수시간 단위(0, 1, 2, ... )로 흐르고, 모든 막대기들은 단위시간당 길이 만큼 움직인다.

아래 그림 1에서처럼 초기(시간 0)에 각 막대기는 직사각형의 왼쪽 변 또는 오른쪽 변에 닿아있다. 

시간이 지남에 따라 각 막대기는 주어진 방향으로 움직이고 

막대기의 양쪽 끝 중에 하나가 직사각형의 왼쪽 변 또는 오른쪽 변에 닿으면 진행하는 방향과 반대 방향으로 계속해서 움직인다.

 

 

 

 

 

철수(그림 1의 검정색 원)는 초기에 가장 아래층막대기 위에 위치하고 있다. 

그리고 아래 조건 1)을 만족하면서 현재 막대기 위에서 움직일 수 있고, 조건 2)를 만족한다면, 하나 위층의 막대기로 올라 갈 수 있다.

조건 1) 현재 위치하고 있는 막대기 위에서는 0시간에 움직일 수 있다. (즉, 막대기 위에서의 움직임은 시간이 걸리지 않는다.)

조건 2) 철수가 현재 위치하고 있는 막대기의 임의의 위치에서 수직으로 이동 했을 때, 

바로 위 층의 막대기 구간 안에 있으면(구간의 양쪽 끝 포함) 0시간에 바로 위 층의 막대기로 수직으로 올라갈 수 있다. 

(즉, 이 조건을 만족해서 하나 위층으로 올라 갈 수 있다면, 올라가는 움직임은 시간이 걸리지 않는다.)

예를 들어서, 아래 그림 2에서처럼 철수는 시간 2에 두 번째 층을 지나 세 번째 층의 막대기로 움직일 수 있다. 

그리고 그림 3에서처럼 시간 4에 네 번째 층을 지나 다섯 번째 층의 막대기에 도달할 수 있다.

 

 

 

 

시간 0의 초기 상태에서 출발해서 철수가 가장 아래층의 막대기에서 가장 위층의 막대기로 올라가는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

 

 

입력형식

첫 번째 줄에 층 수 N(1≤N≤3,000)과 층의 길이 L(1≤L≤3,000, L은 짝수)이 주어진다. 가장 아래층은 1층이고 가장 위층은 N층이다. 다음 N개의 줄 중 i번째 줄에는 층의 막대기의 길이 ℓ(1≤ℓ≤L, ℓ은 짝수)과 초기에 막대기가 움직이는 방향 d(d=0,1)가 주어진다. 여기서, d의 값 0은 왼쪽에서 오른쪽, 1은 오른쪽에서 왼쪽을 의미한다. 또한 초기에 막대기들은 방향이 0인 경우 층의 왼쪽 벽에, 1인 경우 층의 오른쪽 벽에 닿아 있다고 가정한다.

 

출력형식

첫째 줄에 철수가 가장 아래층 막대기에서 가장 위층 막대기로 올라가는데 걸리는 최소 시간을 하나의 정수로 출력한다.

입력 예1	출력 예1
4 6 4 1 2 0 4 0 2 1	0
입력 예2	출력 예2
5 12 4 1 4 0 2 0 2 1 6 0	4

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define Max 5000

int len[Max], edge[Max], min[Max], check[Max];

int main() 
{
    int i, n, m, max_cnt = 0;

    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        scanf("%d %d", &len[i], &edge[i]);
    }

    for (i = 1; i < n; i++) {
        if (edge[i] != edge[i - 1]) {
            if ((m - len[i] - len[i - 1]) / 2 > max_cnt) {
                max_cnt = (m - len[i] - len[i - 1]) / 2;
            }
        }
    }

    printf("%d\n", max_cnt);

    return 0;
}