시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB85262375171728.380%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

3 3
5 1 3
2 4 8
1 1 2

예제 출력 1

RRDLLDRR

예제 입력 2

2 2
2 1
3 4

예제 출력 2

DR
W3sicHJvYmxlbV9pZCI6IjI4NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM2YjBcdWI5YWNcdWIwOThcdWI3N2NcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWIxODBcdWM3NzQgXHVhY2Y1XHVjNmQwXHVjNzQ0IFx1YzZiNFx1YzYwMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWIxODBcdWM3NzQgXHVhY2Y1XHVjNmQwXHVjNzQwIFx1YzU3Y1x1YzY3OFx1YzVkMCBcdWM3ODhcdWFjZTAsIFx1YjJlNFx1YzU5MVx1ZDU1YyBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWFjMDAgXHViOWNlXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViMjkwIFx1YjBhMCBcdWJjYTRcdWNlNThcdWM1ZDAgXHVjNTQ5XHVjNTQ0XHVjNzg4XHViMzU4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNlZTRcdWIyZTRcdWI3ODAgXHVkNjY5XHVhZTA4XHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU1YyBcdWFlMzBcdWJkODRcdWM3NzQgXHViNGU0XHVjNWM4XHViMmU0LiBcdWM3OTBcdWMyZTBcdWM3NTggXHViMjA4IFx1YzU1ZVx1YzVkMCBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YmQ4MFx1YzljMFx1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1NzRcdWMxMWMgXHViODY0XHViN2VjXHVjZjU0XHVjMmE0XHVkMTMwXHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNFx1YmE3NCwgXHVjMTM4XHVjMGMxXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3YWNcdWJiZjhcdWM3ODhcdWIyOTQgXHViODY0XHViN2VjXHVjZjU0XHVjMmE0XHVkMTMwXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmQ4MFx1YzljMFx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzc0XHVhY2UwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgUlx1ZDU4OSBDXHVjNWY0XHVjNzU4IFx1ZDQ1YyBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWM4XHViMmU0LiBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU2MCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1Y2U3OFx1YzVkMFx1YzExYyBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWIyOTQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWFjZmMgXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzY3Y1x1Y2FiZCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWNlNzhcdWM3NDAgXHVkNTVjIFx1YmM4OCZuYnNwO1x1YmMyOVx1YmIzOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWJjMjlcdWJiMzhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1Y2U3OFx1Yzc3NCBcdWM3ODhcdWM1YjRcdWIzYzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjZTc4XHVjNWQwXHViMjk0IFx1YWRmOCBcdWNlNzhcdWM3NDQgXHVjOWMwXHViMDk4XHVhYzA4IFx1YjU0YywgXHVkMGQxXHVjMmI5XHVjNzkwXHVhYzAwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWUzMFx1YzA2OFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjJlNC4gXHViODY0XHViN2VjXHVjZjU0XHVjMmE0XHVkMTMwXHViOTdjIFx1ZDBjNCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTMwXHVjMDY4XHVjNzQwIFx1YzljMFx1YjA5OFx1YWMwNCBcdWNlNzhcdWM3NTggXHVhZTMwXHVjMDY4XHVjNzU4IFx1ZDU2OVx1Yzc3NFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFlMzBcdWMwNjhcdWM3NDQgXHVjOGZjXHViMjk0IFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1YjI5NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjNmMwXHVjOWMxXHVjNWVjXHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBSLCBDICZsZTsgMTAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjZTc4XHVjNzQ0IFx1YzljMFx1YjA5OFx1YWMwOCBcdWI1NGMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTMwXHVjMDY4XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCAxMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhZTMwXHVjMDY4XHVjNzQ0IFx1YzhmY1x1YjI5NCBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgXHVjZTc4XHViZDgwXHVkMTMwIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1YjQxOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzcwNFx1YjI5NCBVLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDAgUiwgXHVjNjdjXHVjYWJkXHVjNzQwIEwsIFx1YzU0NFx1Yjc5OFx1YjI5NCBEXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjg3MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxVTkFQQVJLIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgZ3Jvd24gdGlyZWQgb2YgYWxsIHRoZSBib29rcywgc28gaGUgZGVjaWRlZCB0byBnbyB0byB0aGUgYW11c2VtZW50IHBhcmsgd2l0aCBoaXMgZnJpZW5kcywgZGVzcGl0ZSBub3QgbGlraW5nIHJvbGxlciBjb2FzdGVycy4gV2hpbGUgaGlzIGZyaWVuZHMgYXJlIGhhdmluZyB0aGUgdGltZSBvZiB0aGVpciBsaXZlcyByaWRpbmcgdGhlIGNvYXN0ZXJzLCBNaXJrbyBpcyBzaXR0aW5nIG9uIGEgYmVuY2gsIHdhaXRpbmcgYW5kIHRoaW5raW5nIGFib3V0IHRoZSBwb3NzaWJsZSBwYXRocyBvZiB0aGUgY29hc3RlcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBhbXVzZW1lbnQgcGFyayZyc3F1bztzIGFyZWEgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgdGFibGUgb2YgUiByb3dzIGJ5IEMgY29sdW1ucy4gQSByb2xsZXIgY29hc3RlciBoYXMgdG8gc3RhcnQgZnJvbSB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgYW5kIGVuZCBhdCB0aGUgbG93ZXIgcmlnaHQgY29ybmVyIG9mIHRoZSB0YWJsZS4gRWFjaCBjZWxsIGNhbiBiZSB2aXNpdGVkIGF0IG1vc3Qgb25jZSwgYnV0IG5vdCBhbGwgY2VsbHMgbmVlZCB0byBiZSB2aXNpdGVkLiBJdCBjYW4gY29udGludWUgaXRzIHBhdGggZnJvbSB0aGUgY3VycmVudCBjZWxsIHRvIHRoZSBhZGphY2VudCBvbmUgYWJvdmUsIGJlbG93LCB0byB0aGUgbGVmdCwgb3IgdG8gdGhlIHJpZ2h0IG9mIGl0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGNlbGwgaGFzIGEgcG9zaXRpdmUgaW50ZWdlciB2YWx1ZSBhc3NvY2lhdGVkIHdpdGggaXQsIHNwZWNpZnlpbmcgaG93IGFtdXNpbmcgdGhhdCBjZWxsIGlzIHRvIHZpc2l0b3JzLiBUaGUgdG90YWwgYW11c2VtZW50IHZhbHVlIG9mIHRoZSBjb2FzdGVyIGlzIHRoZSBzdW0gb2YgYW11c2VtZW50IHZhbHVlcyBvZiBhbGwgY2VsbHMgdGhhdCB0aGUgY29hc3RlciB2aXNpdHMuIEhlbHAgTWlya28gZGV0ZXJtaW5lIGFueSBvbmUgb2YgdGhlIG1vc3QgYW11c2luZyBjb2FzdGVycyAob25lcyB3aXRoIHRoZSBtYXhpbXVtIHN1bSkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQyAoMiAmbGU7IFIsIEMgJmxlOyAxMDAwKSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIHRhYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IFIgbGluZXMgY29udGFpbnMgQyBwb3NpdGl2ZSBpbnRlZ2VycyBzbWFsbGVyIHRoYW4gMTAwMCwgc3BlY2lmeWluZyB0aGUgYW11c2VtZW50IHZhbHVlcyBvZiB0aGUgcmVzcGVjdGl2ZSB0YWJsZSBjZWxscy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIGEgc2VxdWVuY2Ugb2YgbGV0dGVycyB3aXRoIG5vIGJsYW5rcy4gVGhlIGxldHRlcnMgc3BlY2lmeSB0aGUgc2VxdWVuY2Ugb2YgZGlyZWN0aW9ucyB0aGF0IHRoZSBjb2FzdGVyIGZvbGxvd3MsIHN0YXJ0aW5nIGZyb20gdGhlIHVwcGVyIGxlZnQgYW5kIGVuZGluZyBhdCB0aGUgbG93ZXIgcmlnaHQgY29ybmVyLiBUaGUgZGlyZWN0aW9ucyB1cCwgcmlnaHQsIGRvd24sIGxlZnQgYXJlIG1hcmtlZCBieSBsZXR0ZXJzICZsc3F1bztVJnJzcXVvOywgJmxzcXVvO1ImcnNxdW87LCAmbHNxdW87RCZyc3F1bzssICZsc3F1bztMJnJzcXVvOywgcmVzcGVjdGl2ZWx5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgc29sdXRpb24gaXNuJnJzcXVvO3QgZ3VhcmFudGVlZCB0byBiZSB1bmlxdWUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #2 5번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: kjp4155