알고리즘 스터디(미완)

Google kick start 2020 Round B 3번째 문제 Robot Path Decoding입니다

 

로봇이 각각 NSEW방향으로 한 칸씩 움직이고 (1, 1)에서 출발한다.

전체 크기는 가로세로 각각 10^9크기의 그리드이다.

또한 X(Y)일때 X는 2~9까지의 숫자이고, 괄호 안의 Y를 X번 반복한다.

예시)

• 2(NWE) is equivalent to NWENWE.
• 3(S2(E)) is equivalent to SEESEESEE.
• EEEE4(N)2(SS) is equivalent to EEEENNNNSSSS.

가로 10^9에서 E방향으로 한칸 움직이면 1이 된다. 1에서 W방향으로 한칸 움직이면 10^9가 된다.

NS도 같다.

여기서 로봇의 최종 좌표를 구하는 문제입니다.

 

C++를 사용한 제 풀이입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stack>

using namespace std;
// N(0, -1), S(0, 1), E(1, 0), W(-1, 0)
string s;
stack<pair<int, pair<long long, long long>>> st;
pair<int, pair<long long, long long>> index, temp;
pair<long long, long long> p;

void MovePos(char c) {
	switch (c) {
	case 'N':
		--p.second;
		break;
	case 'S':
		++p.second;
		break;
	case 'E':
		++p.first;
		break;
	case 'W':
		--p.first;
		break;
	}
}

void solve() {
	cin >> s;

	p.first = 0;
	p.second = 0;

	int mul;

	int n = s.size();

	for (int i = 0; i < n; ++i) {
		if (s[i] == '(') {
			index.second = p;
			st.push(index);
			index.first = 0;
			p.first = 0;
			p.second = 0;
		}
		else if (s[i] == ')') {
			temp = st.top();
			st.pop();
			mul = temp.first;
			p.first = p.first * mul + temp.second.first;
			p.second = p.second * mul + temp.second.second;
		}
		else if (s[i] > '1' && s[i] <= '9') {
			index.first = s[i] - 48;
		}
		else {
			MovePos(s[i]);
		}
	}

	p.first = p.first % 1000000000;
	p.second = p.second % 1000000000;

	p.first = p.first >= 0 ? p.first + 1 : 1000000001 + p.first;
	p.second = p.second >= 0 ? p.second + 1 : 1000000001 + p.second;

	cout << p.first << " " << p.second << "\n";
	return;
}

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

	int t;
	cin >> t;
	for (int i = 1; i <= t; ++i) {
		cout << "Case #" << i << ": ";
		solve();
	}
}

결과는..

첫번째 테스트케이스는 맞는데 두번째가 안맞는걸 보고 long long으로 해야되나 싶었는데 그래도 안되는걸 보니 뭔가 알고리즘이 잘못 된 것 같네요.

40분? 정도 푼 것 같은데 다음에 시간되면 다른 방법으로 다시 풀어봐야겠네요 ㅠㅠㅠ