[BOJ_3101_RN] 토끼의 이동 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/3101

문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ), 구현

해설

이 문제는 토끼가 움직이며 밟는 칸의 값을 다 더하는 문제이다. 직관적인 방법으로는 DP를 이용해 행렬을 다 채운 뒤 이동하며 나오는 값을 다 더해 구할수도있다. 하지만 ( 1 <= N <= 100,000 ) 이라는 조건이 있으므로 100,000 * 100,000 의 메모리를 할당 불가할 뿐더러  의 시간복잡도로는 해결이 불가하다. 이걸 통해 좌표만을 가지고 그 칸의 어떠한 값이 들어갈지 계산할 수 있어야 해결이 가능하다는 것을 알 수 있다.

이 행렬을 오른쪽으로 45도 기울여 다이아몬드 모양으로 보게 된다면 줄마다 수가 지그재그로 연속된다는 것을 알 수 있다. 다이아몬드 모양으로 봤을 때 홀수번째 줄은 오른쪽으로 수가 증가하고 짝수번째 줄은 왼쪽으로 수가 증가한다. 이를 통해 간단한 방식으로 해당 좌표의 값을 알 수 있다. ( 이 때 좌표는 다이아몬드 모양으로 관리한다 )

DP를 통해 각 행마다 최대값을 저장한다. ( DP를 이용하지않고 수식으로 해결이 가능하다. ) 해당 좌표가 주어지면 어떤 수부터 시작되는지 DP값을 참조해 알고 x좌표를 통해 왼쪽으로 증가하는지 오른쪽으로 증가하는지 판단해 y좌표를 통해 값을 얻어낼 수 있다.

시간복잡도

DP를 구하는데 필요한 시간복잡도는  이고 토끼가 이동하는데 필요한 시간복잡도는  이므로 최종 시간복잡도는  로 해결이 가능하다.

토끼의 이동 코드 [ C ]

#include <stdio.h>
typedef long long ll;
char pass[300001];
ll dp[200001];
int n;
ll calc(int x, int y) {
    ll res = 0LL;
    if (x & 1) {
        res = dp[x - 1] + (ll)y;
    } else {
        res = dp[x] - (ll)y + 1LL;
    }
    return res;
}
ll chk(int i) {
    return i > n ? n - i % n : i;
}
int main() {
    int i, j, k, x = 1, y = 1;
    ll res = 1LL;
    scanf("%d%d ", &n, &k);
    for (i = 1; i < n * 2; ++i) {
        dp[i] = dp[i - 1] + chk(i);
    }
    gets(pass);
    for (i = 0; i < k; ++i) {
        switch(pass[i]) {
        case 'U':
            if (x > n) ++y;
            --x;
            break;
        case 'D':
            if (x >= n) -- y;
            ++x;
            break;
        case 'L':
            if (x <= n) --y;
            --x;
            break;
        case 'R':
            if (x < n) ++y;
            ++x;
            break;
        }
        res += calc(x, y);
    }
    printf("%lld", res);
    return 0;
}