백준 파이썬 2873 롤러코스터

import sys

input = sys.stdin.readline
R,C = map(int,input().split())

if R%2 == 1:
    ans = ''
    for r in range(R):
        if r%2 == 0:
            ans += 'R'*(C-1)
        elif r%2 == 1:
            ans += 'D'+'L'*(C-1)+'D'
    print(ans)
elif C%2 == 1:
    ans = ''
    for c in range(C):
        if c%2 == 0:
            ans += 'D'*(R-1)
        elif c%2 == 1:
            ans += 'R'+'U'*(R-1)+'R'
    print(ans)
else:
    min_idx,min_val = [0,0],1000
    for r in range(R):
        if r%2 == 0:
            temp = list(map(int,input().split()))
            for c in range(1,C,2):
                if temp[c] < min_val:
                    min_val,min_idx = temp[c],[r,c]
        elif r%2 == 1:
            temp = list(map(int,input().split()))
            for c in range(0,C,2):
                if temp[c] < min_val:
                    min_val,min_idx = temp[c],[r,c]

    ans = ('R'*(C-1)+'D'+'L'*(C-1)+'D')*(min_idx[0]//2)
    r,c = 2*(min_idx[0]//2),0
    nr,nc = min_idx[0],min_idx[1]
    r_bound = r+1
    while r != r_bound or c != C-1:
        if r < r_bound and [r_bound,c] != min_idx:
            r += 1
            ans += 'D'
        elif r == r_bound and [r_bound-1,c] != min_idx:
            r -= 1
            ans += 'U'
        if c != C-1:
            c += 1
            ans += 'R'

    ans += ('D'+'L'*(C-1)+'D'+'R'*(C-1))*((R-1-min_idx[0])//2)

    print(ans)

1. R이 홀수일때

2. C가 홀수일때

3. R,C 둘다 짝수일때

 

경우의 수를 3개로 나눠서 조건에 맞게 구현하면 됩니다.

 

R,C 둘다 짝수 일때가 중요한데,

모든 좌표를 다 방문할 순 없습니다. 최소 한개의 좌표는 방문하지 못합니다.
그렇다면 최대기쁨을 구하는방법은 최소기쁨인 좌표 한군데만 방문하지 않는것입니다.

그런데, 여기서 알아야 할게 있습니다. 최소기쁨인 칸의 좌표를 [r,c] 라고 했을 때
만약 r+c가 짝수라면, 좌표 [r,c]를 방문하지 않을 뿐 아니라 추가적으로 방문하지 못하는 좌표(홀수)가 생깁니다.
하지만 r+c가 홀수라면, 오직 좌표[r,c] 하나만 방문하지 않습니다.

 

따라서 r+c가 짝수라서 좌표 [r,c]도 방문하지 않고, 추가적으로 홀수 좌표도 방문하지 않는다면
차라리 홀수 좌표 중에서 최소기쁨인 칸을 찾아내서, 그 칸만 방문하지 않으면 됩니다.

 

최소값 근처까지 이동한 후, while 문으로 최소값 근처에서의 이동경로를 구하고 그 다음에 목적지까지 이동하는 식으로 구현하면 됩니다.