์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ๋ฑ€์ด ์„ฑ์žฅํ•˜๋ฉด์„œ ์ƒ๊ธฐ๋Š” ๊ฐ€๋กœ์ง์„ , ์„ธ๋กœ์ง์„ ์„ ๋”ฐ๋กœ ์ €์žฅ.
  • ์ƒˆ๋กญ๊ฒŒ ์ƒ๊ธฐ๋Š” ์ง์„ ์ด ์ด์ „์— ์ €์žฅ๋œ ์ง์„ ์— ๊ฑธ๋ฆฌ๋Š”์ง€ ํ™•์ธ.
  • ์ด๋•Œ, ์ง์„ ์€ ์ •๋ ฌํ•˜์—ฌ ๋ฑ€์ด ๋‚˜์•„๊ฐ€๋Š” ๋ฐฉํ–ฅ์—์„œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์ง์„ ์— ๊ฑธ๋ฆฌ๋„๋ก ํ•˜์ž.

์—ฌ๋‹ด

  • ๊น”๋”ํ•˜๊ฒŒ ๊ตฌํ˜„ํ•˜๊ธฐ์— ๋งค์šฐ ์• ๋ฅผ ๋จน์—ˆ๊ณ , ๊ฐ€๋Šฅํ•˜์ง€๋„ ์•Š์•˜๋‹ค. ๊ทธ๋งŒํผ ๋ถ„๋ฆฌํ•˜์—ฌ ์ƒ๊ฐํ•ด์•ผํ•˜๋Š” ์กฐ๊ฑด๋“ค์ด ๋งŽ๊ณ , ๊ทธ๋ ‡๊ธฐ์— ์‹ค์ˆ˜๋ฅผ ํ•  ๊ฐ€๋Šฅ์„ฑ์ด ๋งค์šฐ ํฌ๋‹ค.
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž์ฒด๋ฅผ ๊ฐ„๋‹จํ•˜๋ฏ€๋กœ, ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค๊ฐ€ ๋œฌ๋‹ค๋ฉด ์‹ค์ˆ˜๋ฅผ ํ•˜์ง€ ์•Š์•˜๋Š”์ง€๋ฅผ ์ค‘์ ์œผ๋กœ ์ฐพ์•„๋ณด๋ฉด ๋  ๊ฒƒ ๊ฐ™๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <set>
 
typedef long long LL;
 
using namespace std;
 
set<pair<LL, pair<LL, LL>>> v, h;
LL l, n, ans, curDir = 1, cr, cc;
 
bool add(int, int);
bool check(LL, LL);
 
int main() {
	cin >> l >> n;
 
	pair<LL, pair<LL, LL>> t[3] = { { l + 1, {-l, l} },{ -l - 1, {-l, l} }, { 0,{0,0} } };
	for (int i = 0; i < 3; i++) {
		h.insert(t[i]);
		v.insert(t[i]);
	}
 
	int a;
	char b;
	bool check = false;
	while (n--) {
		cin >> a >> b;
		if (!add(a, b)) {
			check = true;
			break;
		}
	}
 
	if(!check)
		add(2000000010, 'L');
 
	cout << ans;
	return 0;
}
 
bool add(int t, int dir) {
	LL nr = curDir == 0 ? cr + t : cr - t, nc = curDir == 1 ? cc + t : cc - t;
	if (curDir % 2 == 0) {
		cr += curDir == 0 ? 1 : -1;
		if (!check(nr, cc))
			return false;
 
		curDir == 0 ? v.insert({ cc, {cr, nr} }) : v.insert({ cc, {nr, cr} });
		cr = nr;
	}
	else {
		cc += curDir == 1 ? 1 : -1;
		if (!check(cr, nc))
			return false;
 
		curDir == 1 ? h.insert({ cr, {cc, nc} }) : h.insert({ cr, {nc, cc} });
		cc = nc;
	}
	ans += t;
 
	if ((curDir == 1 && dir == 'L') || (curDir == 3 && dir =='R'))
		curDir = 0;
	else if ((curDir == 2 && dir == 'L') || (curDir == 0 && dir == 'R'))
		curDir = 1;
	else if ((curDir == 3 && dir == 'L') || (curDir == 1 && dir == 'R'))
		curDir = 2;
	else if ((curDir == 0 && dir == 'L') || (curDir == 2 && dir == 'R'))
		curDir = 3;
	return true;
}
 
bool check(LL nr, LL nc) {
	if (curDir % 2 == 0) {
		LL higher = curDir == 0 ? nr : cr, lower = curDir == 0 ? cr : nr;
		if (curDir == 0) {
			for (auto iter = h.begin(); iter != h.end(); iter++) {
				if (lower <= (*iter).first && higher >= (*iter).first && (*iter).second.first <= cc && (*iter).second.second >= cc) {
					ans += (*iter).first - lower + 1;
					return false;
				}
			}
		}
		else {
			auto iter = h.end();
			iter--;
			for (; iter != h.begin(); iter--) {
				if (lower <= (*iter).first && higher >= (*iter).first && (*iter).second.first <= cc && (*iter).second.second >= cc) {
					ans += higher - (*iter).first + 1;
					return false;
				}
			}
			if (lower <= (*iter).first && higher >= (*iter).first && (*iter).second.first <= cc && (*iter).second.second >= cc) {
				ans += higher - (*iter).first + 1;
				return false;
			}
		}
		for (auto iter = v.begin(); iter != v.end(); iter++) {
			int vc = (*iter).first, vlh = (*iter).second.first, vhh = (*iter).second.second;
 
			if (cc == vc && ((higher >= vlh && higher <= vhh) || (lower >= vlh && lower <= vhh) || (higher > vhh && lower < vlh))) {
				ans += curDir == 0 ? vlh - lower + 1 : higher - vhh + 1;
				return false;
			}
		}
	}
	else {
		LL higher = curDir == 1 ? nc : cc, lower = curDir == 1 ? cc : nc;
		if (curDir == 1) {
			for (auto iter = v.begin(); iter != v.end(); iter++)
				if (lower <= (*iter).first && higher >= (*iter).first && (*iter).second.first <= cr && (*iter).second.second >= cr) {
					ans += (*iter).first - lower + 1;
					return false;
				}
		}
		else {
			auto iter = v.end();
			iter--;
			for (; iter != v.begin(); iter--)
				if (lower <= (*iter).first && higher >= (*iter).first && (*iter).second.first <= cr && (*iter).second.second >= cr) {
					ans += higher - (*iter).first + 1;
					return false;
				}
			if (lower <= (*iter).first && higher >= (*iter).first && (*iter).second.first <= cc && (*iter).second.second >= cc) {
				ans += higher - (*iter).first + 1;
				return false;
			}
		}
		for (auto iter = h.begin(); iter != h.end(); iter++) {
			int hh = (*iter).first, hlc = (*iter).second.first, hhc = (*iter).second.second;
 
			if (cr == hh && ((higher >= hlc && higher <= hhc) || (lower >= hlc && lower <= hhc) || (higher > hhc && lower < hlc))) {
				ans += curDir == 1 ? hlc - lower + 1: higher - hhc + 1;
				return false;
			}
		}
	}
	return true;
}