BOJ 3101

05 May 2020 • ProblemSolving

토끼의 이동

문제출처

문제 해석

토끼가 방문하는 칸의 수의 합을 구하는 문제입니다.

1~N2까지의 수가 대각선 순서로 NxN행렬에 채워져 있습니다.

토끼는 처음에 1이 있는 칸에 있고 주어지는 명령대로 이동합니다.

토끼가 행렬을 벗어나는 경우는 없습니다.

설계(20)

N<=100,000이므로 메모리복잡도가 O(N^2)인 2차원 배열을 생성할 수 없습니다.

따라서, 특정 좌표의 값에 바로 매칭시킬 수 있도록 규칙을 찾아야 합니다.

규칙은 다음과 같습니다.

  1. 좌표를 이용하여 몇번째 대각선인지 찾습니다.
  2. 홀수,짝수를 기준으로 해당 숫자를 찾습니다.

이 규칙을 구현하기 위해서 누적합 방법을 이용합니다.

먼저, N번째 대각선까지 칸의 수가 1씩 증가하고, 이후로 1씩 감소합니다.

이 방법으로 각 대각선의 마지막 숫자를 누적합배열에 저장해 놓습니다. 동시에 각 대각선이 몇칸인지 별도로 저장해놓습니다.

1번 규칙은 (0,0)기준 (x+y+1)으로 대각선 인덱스를 찾을 수 있습니다.

그리고 2번 규칙을 적용할 때, 4가지 상태를 기준으로 각각 구현합니다.

  1. 짝수 대각선인 경우
    • 인덱스가 N보다 작거나 같은 경우 이 경우 x==0부터 순차적으로 내려오기 때문에 누적합을 이용하여 해당 숫자를 유추할 수 있습니다.
    • N보다 큰 경우 이 경우, 시작인덱스가 바뀝니다. 규칙을 찾아보면 next%N이 시작 인덱스가 됩니다. 시작 인덱스로부터 순차적으로 내려오기 때문에 위의 경우와 마찬가지로 원하는 숫자를 얻을 수 있습니다.
  2. 홀수 대각선인 경우

    • 인덱스가 N보다 작거나 같은 경우 짝수 대각선과는 달리 아래에서 위로 올라오는 형태를 띄고 있습니다. 따라서 거꾸로 인덱싱을 해주어서 원하는 숫자를 찾습니다.

    • N보다 큰 경우 끝나는 인덱스가 변화하므로, 이에 맞춰서 원하는 숫자를 찾아야 합니다.

구현(40)

코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
using namespace std;
#define MAXN 100001

long long psum[MAXN * 2][2];
char s[MAXN * 3 + 1];
int N, K;
int x, y;
long long ans = 1;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    cin >> N >> K;
    for (int i = 0; i < K; i++) {
        cin >> s[i];
    }
    int cnt = 0;
    for (int i = 1; i < 2 * N; i++) {
        if (i <= N) cnt++;
        else cnt--;
        psum[i][0] = psum[i - 1][0] + cnt;
        psum[i][1] = cnt;
    }
    for (int i = 0; i < K; i++) {
        if (s[i] == 'D') x++;
        else if (s[i] == 'U') x--;
        else if (s[i] == 'R') y++;
        else y--;
        if ((x + y + 1) % 2 == 0) {
            if (x + y + 1 > N) {
                ans += psum[x + y][0] + (x - (x + y + 1) % N) + 1;
            }
            else ans += psum[x + y][0] + x + 1;
        }
        else {
            if (x + y + 1 > N) {
                ans += psum[x + y][0] + (psum[x + y + 1][1] - (x - (x + y + 1) % N));
            }
            else {
                ans += psum[x + y][0] + (psum[x + y + 1][1] - x);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}
디버깅

명령어 입력을 저장할 때, string형으로 한번에 받고자 했으나, 명령어 수가 많을 경우 짤리는 경우를 확인하였습니다.

이를 방지하고자 char배열에 따로 저장하였습니다.

누적합을 만들 때, int형으로 저장한 실수를 하였습니다. 이를 long long형으로 대체하였습니다.

제출결과

8 ms

마무리

규칙을 찾는 구현문제였습니다.

배열을 사용하지 않고,각 좌표의 숫자를 O(1)에 바로 구할 수 있는 부분이 흥미로웠습니다.

 BOJ

Related Posts