취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2528번 문제인 사다리이다.
문제는 아래 링크를 확인하자.

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

시간을 1초씩 흘려보내면서 매 시간마다 다음 층으로 올라갈 수 있을 만큼 올라가는 것을 반복하는 시뮬레이션 코드를 작성해 문제를 해결해보자. 이 때 1초가 지날 때마다 모든 막대기의 위치를 전부 옮기는 작업을 하는 대신 수식을 이용해 각 시각의 현재 층과 다음 층의 막대기의 위치를 계산해줄 것이다.

구체적으로 한 층의 막대기의 움직임은 (해당 층의 길이) - (막대의 길이)만큼 좌로 움직이고 우로 움직이는 것을 반복하므로 그 주기가 위의 값에 2를 곱한 것과 같음을 알 수 있다. 이를 이용하면 시각 T가 주어졌을 때 해당 막대기가 어느 위치에 있는지를 나머지 연산과 간단한 조건문을 이용하여 계산해낼 수 있게 된다. 단, 막대의 길이와 층의 길이가 같은 경우 0으로 나눠 나머지를 구하려는 시도를 하면 안됨에 유의해 구현하자.

좌우로 한번 왕복하는 시간 내로는 다음 층으로 무조건 올라갈 수 있으므로 이와 같은 시뮬레이션 코드의 시간복잡도는 $O(NL)$이고, 이는 문제를 해결하기에 충분한 시간복잡도이다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, L, T;
int l[3001], dir[3001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> L;
	for (int i = 1; i <= N; i++) cin >> l[i] >> dir[i];

	int i = 1;
	while (i < N) {
		if (l[i] == L || l[i + 1] == L) {
			i++;
			continue;
		}

		int curL, curR, curdir = dir[i], nxtL, nxtR, nxtdir = dir[i + 1];
		int curM = T % ((L - l[i]) * 2);
		if (curM >= L - l[i]) curM -= L - l[i], curdir ^= 1;
		if (curdir) curL = curM, curR = curM + l[i];
		else curL = L - curM - l[i], curR = L - curM;

		int nxtM = T % ((L - l[i + 1]) * 2);
		if (nxtM >= L - l[i + 1]) nxtM -= L - l[i + 1], nxtdir ^= 1;
		if (nxtdir) nxtL = nxtM, nxtR = nxtM + l[i + 1];
		else nxtL = L - nxtM - l[i + 1], nxtR = L - nxtM;

		if (max(curL, nxtL) <= min(curR, nxtR)) i++;
		else T++;
	}

	cout << T;
}