BOJ

🖋️ 문제

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 둘째 줄부터 R개 줄에는 각 칸을 지나갈 때 얻을 수 있는 기쁨이 주어진다. 이 값은 1000보다 작은 양의 정수이다.

출력
첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 일 수도 있다.

🤔 접근

1. 가로든 세로든 짝수면 그냥 다 돌면 되겠구나
2. 가로 세로가 짝수라면 절대 다 지나갈 수 없으니 어떤 칸을 안 지나가야 할지 생각해보자
3. 한 칸만 빼고 전부 방문할 수 있다면, 최솟값만 빼고 다 방문하면 되겠네!
4. 근데 한 칸만 제외하고 전부 방문할 수 있는 건 맞을까?
5. (i, j)칸에 대해서 (i+j) % 2 == 1 인 칸들은 전부 해당 칸을 제외하고 전부 방문할 수 있네?
6. 근데 (i+j) % 2 == 0 인 칸을 제외하고 지나가는 것들 중에서 최댓값이 있으면 어떡하지?
7. 아! (i+j) % 2 == 0을 안 지나가려면 무조건 (i+j) % 2 == 1인 칸 하나 이상을 지나가야 하는데, 그럴바에 (i+j) % 2 == 1인 칸 중 하나를 안 지나가고 남은 곳들을 다 지나가는게 무조건 이득이구나!
8. 그렇다면 (i+j) % 2 == 1인 칸 중에서 기쁨이 최소인 곳을 찾아서 그 곳만 빼고 다 지나가게 하자.
9. 빡구현

💻 내 코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
table = []
for _ in range(r):
    clist = list(map(int, input().split()))
    table.append(clist)

rst = ""
if r % 2 == 1: # 가로로 탐색
    for i in range(r):
        if i % 2 == 0:
            rst += ("R" * (c-1))
        else:
            rst += ("D" + ("L" * (c-1)) + "D")
elif c % 2 == 1: # 세로로 탐색
    for j in range(c):
        if j % 2 == 0:
            rst += ("D" * (r-1))
        else:
            rst += ("R" + ("U" * (r-1)) + "R")

else:
    min_value = 1000
    for i in range(r):
        for j in range(c):
            if ((i+j) != 0) and ((i+j) != (r+c)) and ((i + j) % 2 == 1) and (table[i][j] < min_value):
                min_value = table[i][j]
                blank = (i, j)
    # 롤러코스터를 타자
    # blank 전까지 일단 타자
    rst += ('R'*(c-1) + 'D' + 'L' * (c-1) + 'D') * (blank[0]//2)
    rst += ('DRUR') * (blank[1] // 2)
    if blank[0] % 2 == 0:
        rst += 'DR'
    else:
        rst += 'RD'
    rst += ('RURD') * ((c//2 - 1) - (blank[1] // 2))
    rst += ('D' + 'L'*(c-1) + 'D' + 'R' * (c-1)) * ((r//2-1) - (blank[0]//2))

print(rst)

👍 제출

1. 하나씩 전부 일일히 방문하면서 DURL을 하나씩 추가함.
2. 잘 못 구현함
3. 가로 세로 둘 다 짝수일 때만 blank를 찾아야 하는데 그냥 다 찾음...
4. 맞았습니다~