https://www.acmicpc.net/problem/2873
시간 1초, 메모리 256MB
input :
- R C (2 ≤ R, C ≤ 1000)
- 기쁨 (0 < 기쁨 < 1000)
output :
- 어떻게 움직이면 되는지를 출력( 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 )
조건 :
- 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착
- 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동
- 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.
- 각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합
길고 긴 사투였다....
처음엔 홀수 인 경우엔 모든 칸을 확인 할 수 있다는 것을 확인하고.
짝수인 경우에가 문제였다.ㅣ 마지막 1칸만 비우면 되는 것 아닌가 하는 안일한 생각을 가지다가. 다른 경우가 발생되는 것을 보고 뒷골이 아팠다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
다른 풀이들을 보다가... 도당체 모르겠어서 백준님의 풀이를 보게 되었다. 큰 격자를 작은 격자로 만드는 풀이인데 가장 이해하기 편했다.
이를 구현만 하면 되는것인데....
우선 시작점, 도착점으로 나뉜다.
시작점에서 이동하는 것들을 front 변수에.
도착점까지의 이동경로는 back에 저장하도록 하겠다.
첫 번째. 가장 작은 값을 찾은 후. 그 값을 포함하는 행 까지 격자모양을 줄인다.
front += (('R' * (m - 1) + 'D') + ('L' * (m - 1) + 'D')) * (x // 2)
back += (('D' + 'L' * (m - 1)) + ('D' + 'R' * (m - 1))) * ((n - x - 1) // 2)시작 지점에서 아래로 2행씩 이동하는 방법을 나타내는 것,
도착 지점에서 2행 위에 존재하는 지점에서 도착지점까지 움직이는 방법을 저장한다.
그렇게 되면 남은 이동할 것은 2행 남은 곳에서 움직이는 것이다.
이때에 움직이는 경로가 패턴이 존재한다.
시작지점의 경우에는 DRUR 로 움직이며 2칸을 가로로 이동한다.
0 -> 2 -> 4 ....
도착 지점까지 움직이는 경우는 RURD로 동일하게 2칸을 가로로 이동한다.
1 -> 3 -> 5 ...
그리고 이 움직임을 행의 위치를 바꾸지 않기 때문에 별 다른 걸 생각하지 않아도 된다.
target이 위에 행에 존재하는지 아래 행에 존재하는지랑 상관없이 이동은 위의 경우를 받아서 움직이고.
마지막 2 * 2 격자 무늬 가 생겼을 때.
target이 칼럼0에 존재한다면 RD
target이 칼럼1에 존재한다면 DR로 움직인다.
if y % 2 == 0:
front += 'DRUR' * (y // 2) + 'RD'
back = 'RURD' * ((m - y - 2) // 2) + back
else:
front += 'DRUR' * ((y - 1) // 2) + 'DR'
back = 'RURD' * ((m - y - 1) // 2) + backback의 경우에 마지막 2행이 남았을 때 움직이는 것이. / 이 전에 계산한 2행씩 움직이는 것보다 먼저 행해져야 하기 때문에
back = __ + back 로 계산이 이루어져야 한다.
사실.. 백준님 그림 보는 것이 제일 좋다.....
위의 back 계산에서 하나를 빼먹는 바람에 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 헤멨다....
그리고 나눗셈에 유의하자... 이것도 헤멨다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
import sys
n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
graph.append(list(map(int, sys.stdin.readline().split())))
ret = ''
front = ''
back = ''
if n % 2 == 1:
ret += (('R' * (m - 1) + 'D') + ('L' * (m - 1) + 'D')) * (n // 2) + 'R' * (m - 1)
elif m % 2 == 1:
ret += (('D' * (n - 1) + 'R') + ('U' * (n - 1) + 'R')) * ((n - 1) // 2) + 'D' * (n - 1)
else:
score = 999
x, y = -1, -1
for i in range(0, n, 2):
for j in range(1, m, 2):
if score > graph[i][j]:
x = i
y = j
score = graph[i][j]
for i in range(1, n, 2):
for j in range(0, m, 2):
if score > graph[i][j]:
x = i
y = j
score = graph[i][j]
front += (('R' * (m - 1) + 'D') + ('L' * (m - 1) + 'D')) * (x // 2)
back += (('D' + 'L' * (m - 1)) + ('D' + 'R' * (m - 1))) * ((n - x - 1) // 2)
if y % 2 == 0:
front += 'DRUR' * (y // 2) + 'RD'
back = 'RURD' * ((m - y - 2) // 2) + back
else:
front += 'DRUR' * ((y - 1) // 2) + 'DR'
back = 'RURD' * ((m - y - 1) // 2) + back
ret = front + back
print(ret)
