시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 15 6 (40%) 4
문제
민식이는 책을 읽는 것에 싫증이 나서, 롤러코스터를 싫어하지만 놀이 공원에 친구들과 함께 놀러가기로 했다. 친구들이 롤러코스터를 타는 동안, 민식이는 롤러코스터가 만들어질 수 있는 경로를 생각하고 있었다. 놀이공원은 $R$개의 가로줄과 $C$개의 세로줄의 표 형태로 나타내질 수 있다. 롤러코스터는 가장 왼쪽 위의 지점에서 시작해서, 가장 오른쪽 아래의 지점에서 끝이 난다. 각 칸은 최대 한 번 지나갈 수 있지만, 무조건 지나가야만 하는 것은 아니다. 롤러코스터는 각 칸에서 인접한 네 방향(위, 아래, 왼쪽, 오른쪽)으로 움직일 수 있다. 각 칸에는 양의 정수가 있는데, 롤러코스터가 그 칸을 지나는 경우의 재밌음의 수치이다. 롤러코스터의 가치는 그 롤러코스터가 지나는 칸들의 재밌음 수치의 합이 된다. 민식이를 도와 최대 가치를 가지는 롤러코스터의 경로를 알아내자.
입력
첫 번째 줄에 놀이공원의 크기 $R$, $C$가 순서대로 주어진다. $(2 \le R, C \le 1\,000)$ 두 번째 줄부터 $R$개의 줄에 걸쳐 놀이공원의 각 칸의 숫자가 주어진다. 주어지는 모든 숫자는 $1\,000$ 이하의 양의 정수이다.
출력
최대 가치를 가지는 롤러코스터의 경로를 문자열로 출력한다. 가장 왼쪽 위의 칸에서부터 오른쪽 아래의 칸으로 이동하는 경로를 위로 움직이는 경우 ‘U’, 아래로 움직이는 경우 ‘D’, 왼쪽으로 움직이는 경우 ‘L’, 오른쪽으로 움직이는 경우 ‘R’의 문자를 이용해 표현한다. 답이 유일하지 않을 수 있다.
힌트
#### 채점 70%의 점수에 해당하는 입력 데이터는 $R, C \le 30$을 만족한다. #### 예제 입력 1 ``` 3 3 5 1 3 2 4 8 1 1 2 ``` #### 예제 출력 1 ``` RRDLLDRR ``` #### 예제 입력 2 ``` 2 2 2 1 3 4 ``` #### 예제 출력 2 ``` DR ```