[BOJ/Gold 2] 백준 3101 토끼의 이동(C++)

문제 링크

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

3101번: 토끼의 이동

문제

1부터 N2까지 수가 지그재그 대각선 순서로 N*N 행렬에 채워져 있다. 아래 그림은 N=6일 때, 행렬의 모습이다.

토끼는 지금 1이 있는 칸에 있다. 토끼는 인접한 칸으로 점프할 수 있다. (위, 아래, 오른쪽, 왼쪽)

토끼가 점프한 방법이 주어졌을 때, 토끼가 방문한 칸에 있는 수의 합을 구하는 프로그램을 작성하시오. 같은 칸을 여러 번 방문할 경우에도, 방문할 때 마다 더해야 한다. 토끼가 행렬을 벗어나는 경우는 없다.

입력

첫째 줄에 N, K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ 300,000) N은 행렬의 크기, K는 토끼가 점프한 횟수이다.

둘째 줄에는 'U','D','L','R'로 이루어진 문자열이 주어진다. 이 문자열의 길이는 K이며, 토끼가 점프한 방향이다.

출력

첫째 줄에, 방문한 칸의 수의 합을 출력한다. 이 값은 32비트 정수를 넘을 수도 있다.

예제 입력 1

6 8
DDRRUULL

예제 출력 1

47

예제 입력 2

3 8
DDRRUULL

예제 출력 2

41

예제 입력 3

6 10
RRRRRDDDDD

예제 출력 3

203

알고리즘 분류

• 구현
• 수학

풀이

https://kukekyakya.tistory.com/m/339

백준 3101 : 토끼의 이동

위 형님꺼를 참고해서 풀었다.

우선 N이 10만이므로, 실제로 배열을 선언해서 풀면 당연히 메모리 초과가 날 것이고, 그렇게 풀라고 의도하고 출제한 문제였다면 골드2가 아니라 브론즈2였을 것이다.

우리는 좌표를 통해서 좌표에 위치한 숫자를 알아내야 한다.

우선 가만히 행렬을 보면, 대각선을 따라서 값이 증가하는 것을 알 수 있다. 첫 번째 대각선은 1, 두 번째 대각선은 2, 3, 세 번째 대각선은 4, 5, 6, ...

그리고 홀수 번째 대각선은 위에서 아래로 향할 때 값이 증가하고, 짝수 번째 대각선은 위에서 아래로 향할 때 값이 감소한다.

그리고 두 번째 대각선의 맨 위의 값은 2, 세 번째 대각선의 맨 위의 값은 6, 네 번째 대각선의 맨 위의 값은 7, ...

따라서, X좌표가 증가할 때마다 홀수 번째 대각선에서는 숫자가 1씩 증가하고, 짝수 번째 대각선에서는 숫자가 1씩 감소한다.

그럼 우리는 각 대각선마다 시작하는 숫자만 알면 그 뒤에 이어지는 숫자는 수식으로 구할 수 있다.

대각선의 순번이 D라고 하면,

홀수 번째 대각선은 (D * (D + 1)) / 2에서 (X - 1)을 뺀 값이고,

짝수 번째 대각선은 (D * (D - 1)) / 2에서 X를 더한 값이다.

그리고, D가 N보다 커질 경우, 구한 값에서 (D - N) * (D - N)을 뺀다.

생각하는 게 어려운 문제였고 비슷한 문제가 나올 경우를 대비해서 차라리 아예 값을 구하는 수식을 외워 둬야겠다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100005
#define LL long long
#define INF 1e9

using namespace std;
LL N, K;
LL Diagonal = 1; // (1, 1)이 속해 있는 대각선은 무조건 1번째 대각선
string S;
pair<LL, LL> Rabbit = make_pair(1, 1); // 토끼의 처음 위치는 (1, 1)
LL answer = 1; // 처음에 (1, 1), 즉 1을 방문했으므로 초기값은 1이며, 32비트 정수를 넘을 수 있다고 하였으므로 long long형으로 지정한다.

LL Find_Number(LL Y, LL X) {
	if (Diagonal % 2 == 0) {
		// 짝수번째 대각선인 경우
		if (Diagonal > N) {
			// 대각선 번호가 N을 넘어간 경우 값에서 (대각선 - N) * (대각선 - N)을 빼준다.
			return (((Diagonal * (Diagonal - 1)) / 2) + Y - ((Diagonal - N) * (Diagonal - N)));
		}
		return (((Diagonal * (Diagonal - 1)) / 2) + Y); // (대각선 * (대각선 - 1)) / 2 + X좌표를 더해준 값이 (X, Y)의 값이 된다.
	}
	else if (Diagonal % 2 == 1) {
		// 홀수번째 대각선인 경우
		if (Diagonal > N) {
			return (((Diagonal * (Diagonal + 1)) / 2) - Y + 1 - ((Diagonal - N) * (Diagonal - N)));
		}
		return (((Diagonal * (Diagonal + 1)) / 2) - (Y - 1)); // (대각선 * (대각선 + 1)) / 2 - (X - 1)좌표를 더해준 값이 (X, Y)의 값이 된다.
	}
}

int main() {
	FIRST
	cin >> N >> K;
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
		LL CurY = Rabbit.first;
		LL CurX = Rabbit.second;
		LL nextY, nextX;
		if (S[i] == 'U') {
			// 위로 한 칸 이동하면 이전 대각선으로 이동한다.
			Diagonal--;
			nextY = CurY - 1;
			nextX = CurX;
			answer += Find_Number(nextY, nextX);
		}
		else if (S[i] == 'D') {
			// 아래로 한 칸 이동하면 다음 대각선으로 이동한다.
			Diagonal++;
			nextY = CurY + 1;
			nextX = CurX;
			answer += Find_Number(nextY, nextX);
		}
		else if (S[i] == 'L') {
			// 왼쪽으로 한 칸 이동하면 이전 대각선으로 이동한다.
			Diagonal--;
			nextY = CurY;
			nextX = CurX - 1;
			answer += Find_Number(nextY, nextX);
		}
		else if (S[i] == 'R') {
			// 오른쪽으로 한 칸 이동하면 다음 대각선으로 이동한다.
			Diagonal++;
			nextY = CurY;
			nextX = CurX + 1;
			answer += Find_Number(nextY, nextX);
		}
		Rabbit = make_pair(nextY, nextX);
	}
	cout << answer << "\n";

	return 0;
}