[ SWEA 5357 ] 터널 속의 기차 (C++)

SWExpertAcademy의 터널 속의 기차(5357 / D5) 문제이다.

[ 문제풀이 ]

터널 안이 항상 불이 켜져 있는 상태로 유지되기 위해서 불을 켜야 하는 차량의 최소 횟수를 구해야 하는 문제이다.

먼저, 반드시 불이 켜져 있어야만 하는 차량들이 있다.

바로, 기차의 첫 번째 차량과 마지막 차량이다. 왜냐하면 반드시 다음과 같은 경우가 필연적으로 발생하기 때문이다.

.

위와 같이 그림으로 표현해 본다고 했을 때,

.

위와 같은 상황이 반드시 발생하기 때문이다.

위의 2개의 그림에서 위쪽에 있는 그림은, 기차가 터널로 처음 들어가는 순간, 즉, 첫 번째 차량만이 터널 안에 존재하는 순간이다. 이런 경우가 반드시 있기 때문에, 첫 번째 차량의 불은 반드시 켜져 있어야 한다.

반드시 아래쪽에 있는 그림은, 기차가 터널에서 모두 다 빠져나오고, 마지막 차량만이 터널 안에 존재하는 순간이다.

이런 경우 또한 반드시 있기 때문에, 마지막 차량의 불은 반드시 켜져 있어야 한다.

그럼 이제 불을 언제 켜야 하는지 알아보자.

어떤 차량이 어떤 순간에 불을 켜야하는지가 궁금한 것이니, 불이 켜져 있는 차량보다는 불이 꺼져 있는 차량에 대해서 생각을 해보자. 현재 어떤 차량이 불이 꺼져있는 상태이다. 그럼 이 차량은 언제 불을 켜야할까 ??

가장 쉽게 생각해 볼 수 있는 것은, "터널의 길이보다 이 차량의 길이가 더 긴 상황" 을 떠올릴 수 있다.

이 경우에는 당연하게도 불을 켜줘야 한다. 하지만 단순히 차량과 터널의 길이로만 비교를 할 수는 없다.

그럼 초점을 "터널 안에서, 불이 꺼져 있는 시간" 에 맞춰보자. 기차의 한 차량의 길이가 x 이고, 이 차량에 불이 꺼져 있다고

생각을 해보자. 그럼 최소, 터널 안에서 x초 동안은 불이 꺼져 있다는 것을 알 수 있다.

그런데, 이 x 값이 터널의 길이보다 더 크다면 ?? 불을 켜줘야 하는 것이다.

하나의 예를 들어보자. 기차의 차량이 5개가 있고 각각의 길이는 [ 1, 2, 3, 4, 5 ] 이다. 터널의 길이는 3이다.

불이 켜져 있는 차량은 1번 차량과 5번 차량만 켜져 있다고 가정해보자.

그럼, 2번 차량이 들어오는 순간을 생각해보자. 2번 차량은 불이 꺼져있고, 길이가 2이다. 즉 ! 최소 2초 동안은 터널 안에서 불이 꺼져 있는 시간이 2초 라는 것을 알 수 있다. 하지만 터널의 길이는 3이기 때문에, 아직 불을 켤 필요는 없다.

실제로, 1번 차량에 의해서 2번 차량은 불을 켜지 않아도 된다. 하지만 1번 차량이 터널을 빠져 나가고 3번 차량이 들어오는 경우를 생각해보자.

현재, 터널 안에서 불이 꺼져 있는 시간은 2초이고, 3번 차량 또한 불이 꺼져 있기 때문에, 이 길이 만큼을 더해주게 되면

2 + 3 = 5초 동안 터널안에서 불이 꺼져 있다는 것을 알 수 있다. 터널의 길이인 '3'보다 불이 꺼져있는 시간인 '5'가 더 크기 때문에 이 경우에는 불을 켜줘야 한다는 것을 의미한다. 3번 차량은 반드시 불을 켜야한다는 것이다. 불을 켜는 순간 터널 안에서 불이 꺼져있는 순간은 0으로 초기화를 시켜주어야 한다.

4번 차량을 확인해보자. 길이가 4이고, 불이 꺼져있으므로, 불이 꺼져 있는 시간을 더해보면 0 + 4 = 4 가 된다. 이는 터널의 길이인 '3'보다 더 크기 때문에, 반드시 불을 켜줘야 하는 경우이다. 4번 차량 또한 반드시 불을 켜줘야 한다.

이런식으로 불이 꺼져 있는 시간과 터널의 길이를 비교하면서 불을 키게 되면 이 횟수가 최소가 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, H, Answer;
int Train_Len[MAX];
int Light[MAX];
 
void Initialize()
{
    Answer = 0;
    memset(Light, 0, sizeof(Light));
}
 
void Input()
{
    cin >> N >> H;
    for (int i = 0; i < N; i++) cin >> Train_Len[i];
    for (int i = 0; i < N; i++) cin >> Light[i];
}
 
void Solution()
{
    if (Light[0] == 0) 
    { 
        Light[0] = 1; 
        Answer++; 
    }
    if (Light[N - 1] == 0)
    {
        Light[N - 1] = 1;
        Answer++;
    }
    
    int Off_Time = 0;
    for (int i = 0; i < N; i++)
    {
        if (Light[i] == 1) Off_Time = 0;
        else Off_Time = Off_Time + Train_Len[i];
 
        if (Off_Time >= H)
        {
            Light[i] = 1;
            Answer++;
            Off_Time = 0;
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}