백준 31287번 장난감 강아지

처음에는 그냥 n번안에 원점을 돌아오면 되는거 아닌가 싶었지만 당연히 아니었고

조금더 생각을 해보니 여러번을 움직여야 원점으로 돌아오는 경우도 있다는걸 알았다.

 

이제 문제는 k가 10^9이니 k번을 전부 돌수 없다는 건데 검사를 n번만 해도 충분하다.

그냥 직관적으로 그럴것같았고 정확한 원리는 이해가 되지 않았는데

 

다른사람이 쓴 해설을 좀 읽다보니 이해가 됐다.

문자열을 순회를 한번 했을때 원점으로 돌아온다면 상관없겠지만

문자열을 순회를 한번 했을때 원점이 아니라면(1이라도 이동되었다면) 이는 n번 이후에는 원점에서 n이상 떨어진 위치에 있다는 의미가 된다.

그런데 문자열로 한번에 최대 n만큼만 이동이 가능하기때문에 n번을 넘게 검사할 필요가 없는것이다.

 

#include <iostream>
#include <string>

using namespace std;
#define FAST_IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);

int main(void) {
	FAST_IO;
	int n, k;
	string str;
	cin >> n >> k;
	cin >> str;
	int row = 0, col = 0;
	int result = 0;
	for (int count = 0; count < k && count < n; count++) {
		for (const char& i : str) {
			if (i == 'U') row++;
			else if (i == 'D') row--;
			else if (i == 'R')col++;
			else col--;
			if (row == 0 && col == 0)
			{
				result = 1;
				break;
			}

		}
        if (result == 1) break;
	}

	if (result) {
		cout << "YES";
	}
	else {
		cout << "NO";
	}
	return 0;
}