[백준/BOJ] 백준 2528번 : 사다리

www.acmicpc.net/problem/2528

2528번: 사다리

각 층마다 막대의 왼쪽, 오른쪽 위치와 방향을 저장하고, 시작층부터 위층으로 올라갈 수 있으면 위층으로 올라가고 그렇지 않으면 막대들을 1초 움직이는 방법을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int N, L;
vector<pair<pair<int, int>, int>> stick; //((막대기의 왼쪽위치, 오른쪽위치), 방향)

//현재 위치 이상 층을 1초 움직인다
void Move(int here) 
{
	for (int i = here; i < N; i++)
	{
		if (stick[i].second == 0) //오른쪽 방향으로 이동하는 막대일때
		{
			stick[i].first.first++;
			stick[i].first.second++;

			if (stick[i].first.second == L) //오른쪽 끝에 닿았을때, 방향 변경
			{
				stick[i].second = 1;
			}
		}

		else //왼쪽 방향으로 이동하는 막대일때
		{
			stick[i].first.first--;
			stick[i].first.second--;

			if (stick[i].first.first == 0) //왼쪽 끝에 닿았을때, 방향 변경
			{
				stick[i].second = 0;
			}
		}
	}
}

//올라갈 수 있으면 윗층으로 올라간다
int Go(int here)
{
	int there = here + 1;

	int here_left = stick[here].first.first;
	int here_right = stick[here].first.second;

	int there_left = stick[there].first.first;
	int there_right = stick[there].first.second;

	if (there_left <= here_left && here_right <= there_right)
		return there;

	if (here_left <= there_left && there_right <= here_right)
		return there;

	if (there_left <= here_left && here_left <= there_right)
		return there;

	if (there_left <= here_right && here_right <= there_right)
		return there;

	return here;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N >> L;

	for (int i = 0; i < N; i++)
	{
		int l, d;
		int left, right;
		cin >> l >> d;

		if (d == 0) //오른쪽 방향으로 움직이는 막대일때
		{
			left = 0;
			right = l;
		}

		else //왼쪽 방향으로 움직이는 막대일때
		{
			left = L - l;
			right = L;
		}

		stick.push_back(make_pair(make_pair(left, right), d));
	}

	int result = 0;
	int here = 0; //시작층
	int dest = N - 1; //꼭대기 층

	while (1)
	{
		if (here == dest) //꼭대기층에 도착 했을때
			break;

		int ret = Go(here);

		//올라갈 수 없을때
		if (ret == here)
		{
			Move(here); //막대들을 1초 움직인다
			result++; //1초 증가
		}

		else //올라갈 수 있을때
		{
			here = ret;
		}
	}

	cout << result;


	return 0;
}