이번 문제는 수학적으로 접근하여 각 인덱스에 들어갈 숫자를 그때그때 계산하여 더하는 방식으로 해결하였다. 처음에는 문제에서 제시한 행렬을 만드는 함수를 먼저 호출하고, 만들어진 행렬을 돌며 값을 더하는 방식으로 접근하였지만, 메모리 초과가 발생하였다.

행렬 전체를 만드는 것이 아님을 깨닫고, 행렬을 오른쪽 위에서 왼쪽 아래로 대각선을 모두 그어보았고, 모든 대각선 안에 있는 수들이 연속적이라는 규칙을 찾을 수 있었다. 또한 이 안에서 n번 대각선 이전까지는 짝수번째 대각선에서의 값은 대각선을 시작하는 수 + y좌표-1을 가지고, 홀수번째 대각선에서의 값은 대각선을 시작하는 수 + x좌표-1을 가진다는 것을 찾을 수 있었고, n번 대각선 이후부터는 짝수번째 대각선에서의 값은 대각선을 시작하는 수 + (n-x좌표)를, 홀수번째 대각선에서의 값은 대각선을 시작하는 수 + (n-y좌표)를 가진다는 것을 알 수 있었다.

이를 통해 각 좌표에 해당하는 수를 그때그때 계산하여 해결하였다.

Code

처음 코드 (메모리 초과)

n, k = map(int, input().split())
commands = list(str(input()))
grid = [[0 for _ in range(n)] for _ in range(n)]
dy, dx = [0, 1, 1, -1], [1, -1, 0, 1]
rdy, rdx = [0, 1, 0, -1], [1, 0, -1, 0]
mapping = {'R': 0, 'D': 1, 'L': 2, 'U': 3}
grid[0][0] = 1
rabbit = [0, 0]
def make_grid(y, x, d):
    ny, nx = y+dy[d], x+dx[d]
    if 0 <= ny < n and 0 <= nx < n and grid[ny][nx] == 0:
        grid[ny][nx] = grid[y][x]+1
        if d == 0 or d == 2:
            make_grid(ny, nx, (d+1)%4)
        else:
            make_grid(ny, nx, d)
    else:
        cnt = 0
        flag = False
        while True:
            if cnt > 4:
                break
            if 0 <= y+dy[d] < n and 0 <= x+dx[d] < n and not grid[y+dy[d]][x+dx[d]]:
                flag = True
                break
            d = (d+1)%4
            cnt += 1
        if flag:
            ny, nx = y+dy[d], x+dx[d]
            grid[ny][nx] = grid[y][x]+1
            if d == 0 or d == 2:
                make_grid(ny, nx, (d+1)%4)
            else:
                make_grid(ny, nx, d)
        else:
            return
def move_rabbit():
    global rabbit
    result = 1
    for command in commands:
        d = mapping[command]
        y, x = rabbit
        ny, nx = y+rdy[d], x+rdx[d]
        if 0 <= ny < n and 0 <= nx < n:
            result += grid[ny][nx]
            rabbit = [ny, nx]
    return result
make_grid(0, 0, 0)
print(move_rabbit())

정답 코드

n, k = map(int, input().split())
commands = list(str(input()))
dy, dx = [0, 1, 1, -1], [1, -1, 0, 1]
rdy, rdx = [0, 1, 0, -1], [1, 0, -1, 0]
mapping = {'R': 0, 'D': 1, 'L': 2, 'U': 3}
rabbit = [1, 1]
firsts = [0 for _ in range(n*2)]
firsts[1] = 1
answer = 1
def find_value(idx):
    if idx <= n:
        return idx
    return n-idx%n
def move_rabbit(y, x):
    global answer
    line = y+x-1
    first = firsts[line]
    if line <= n:
        if line%2 == 0:
            answer += (first+y-1)
        else:
            answer += (first+x-1)
    else:
        if line%2 == 0:
            answer += (first+n-x)
        else:
            answer += (first+n-y)
for i in range(2, n*2):
    firsts[i] = firsts[i-1]+find_value(i-1)
for command in commands:
    d = mapping[command]
    rabbit[0] += rdy[d]
    rabbit[1] += rdx[d]
    move_rabbit(rabbit[0], rabbit[1])
print(answer)