시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1310 353 267 29.180%

문제

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

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

이 부지는 직사각형 모양이고, 상근이는 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
W3sicHJvYmxlbV9pZCI6IjI4NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM2YjBcdWI5YWNcdWIwOThcdWI3N2NcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWIxODBcdWM3NzQgXHVhY2Y1XHVjNmQwXHVjNzQ0IFx1YzZiNFx1YzYwMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWIxODBcdWM3NzQgXHVhY2Y1XHVjNmQwXHVjNzQwIFx1YzU3Y1x1YzY3OFx1YzVkMCBcdWM3ODhcdWFjZTAsIFx1YjJlNFx1YzU5MVx1ZDU1YyBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWFjMDAgXHViOWNlXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViMjkwXHViMGEwIFx1YmNhNFx1Y2U1OFx1YzVkMCBcdWM1NDlcdWM1NDRcdWM3ODhcdWIzNTggXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2VlNFx1YjJlNFx1Yjc4MCBcdWQ2NjlcdWFlMDhcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTVjIFx1YWUzMFx1YmQ4NFx1Yzc3NCBcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWIyMDggXHVjNTVlXHVjNWQwIFx1YmNmNFx1Yzc3NFx1YjI5NCBcdWM3NzQgXHViZDgwXHVjOWMwXHViOTdjIFx1YWQ2Y1x1YjllNFx1ZDU3NFx1YzExYyBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWI5N2MgXHViOWNjXHViNGUwXHViMmU0XHViYTc0LCBcdWMxMzhcdWMwYzFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzdhY1x1YmJmOFx1Yzc4OFx1YjI5NCBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViZDgwXHVjOWMwXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NzRcdWFjZTAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBSXHVkNTg5IENcdWM1ZjRcdWM3NTggXHVkNDVjIFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YzhcdWIyZTQuIFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWNlNzhcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjZTc4XHVjNWQwXHVjMTFjIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YWNmYyBcdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjdjXHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWQ1NWMgXHViYzg4Jm5ic3A7XHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjZTc4XHVjNzc0IFx1Yzc4OFx1YzViNFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWNlNzhcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1Y2U3OFx1Yzc0NCBcdWM5YzBcdWIwOThcdWFjMDggXHViNTRjLCBcdWQwZDFcdWMyYjlcdWM3OTBcdWFjMDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTMwXHVjMDY4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMmU0LiBcdWI4NjRcdWI3ZWNcdWNmNTRcdWMyYTRcdWQxMzBcdWI5N2MgXHVkMGM0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFlMzBcdWMwNjhcdWM3NDAgXHVjOWMwXHViMDk4XHVhYzA0IFx1Y2U3OFx1Yzc1OCBcdWFlMzBcdWMwNjhcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWUzMFx1YzA2OFx1Yzc0NCBcdWM4ZmNcdWIyOTQgXHViODY0XHViN2VjXHVjZjU0XHVjMmE0XHVkMTMwXHViMjk0IFx1YzViNFx1YjViYlx1YWM4YyBcdWM2YzBcdWM5YzFcdWM1ZWNcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IFIsIEMgJmxlOyAxMDAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWNlNzhcdWM3NDQgXHVjOWMwXHViMDk4XHVhYzA4IFx1YjU0YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFlMzBcdWMwNjhcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDEwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFlMzBcdWMwNjhcdWM3NDQgXHVjOGZjXHViMjk0IFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWNlNzhcdWJkODBcdWQxMzAgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjZTc4XHVjNzNjXHViODVjIFx1YzViNFx1YjViYlx1YWM4YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzQgXHViNDE4XHViMjk0XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzA0XHViMjk0IFUsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBSLCBcdWM2N2NcdWNhYmRcdWM3NDAgTCwgXHVjNTQ0XHViNzk4XHViMjk0IERcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWM3NDAgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwIFx1Yzc3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMVU5BUEFSSyIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIGdyb3duIHRpcmVkIG9mIGFsbCB0aGUgYm9va3MsIHNvIGhlIGRlY2lkZWQgdG8gZ28gdG8gdGhlIGFtdXNlbWVudCBwYXJrIHdpdGggaGlzIGZyaWVuZHMsIGRlc3BpdGUgbm90IGxpa2luZyByb2xsZXIgY29hc3RlcnMuIFdoaWxlIGhpcyBmcmllbmRzIGFyZSBoYXZpbmcgdGhlIHRpbWUgb2YgdGhlaXIgbGl2ZXMgcmlkaW5nIHRoZSBjb2FzdGVycywgTWlya28gaXMgc2l0dGluZyBvbiBhIGJlbmNoLCB3YWl0aW5nIGFuZCB0aGlua2luZyBhYm91dCB0aGUgcG9zc2libGUgcGF0aHMgb2YgdGhlIGNvYXN0ZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgYW11c2VtZW50IHBhcmsmcnNxdW87cyBhcmVhIGNhbiBiZSByZXByZXNlbnRlZCBhcyBhIHRhYmxlIG9mIFIgcm93cyBieSBDIGNvbHVtbnMuIEEgcm9sbGVyIGNvYXN0ZXIgaGFzIHRvIHN0YXJ0IGZyb20gdGhlIHVwcGVyIGxlZnQgY29ybmVyIGFuZCBlbmQgYXQgdGhlIGxvd2VyIHJpZ2h0IGNvcm5lciBvZiB0aGUgdGFibGUuIEVhY2ggY2VsbCBjYW4gYmUgdmlzaXRlZCBhdCBtb3N0IG9uY2UsIGJ1dCBub3QgYWxsIGNlbGxzIG5lZWQgdG8gYmUgdmlzaXRlZC4gSXQgY2FuIGNvbnRpbnVlIGl0cyBwYXRoIGZyb20gdGhlIGN1cnJlbnQgY2VsbCB0byB0aGUgYWRqYWNlbnQgb25lIGFib3ZlLCBiZWxvdywgdG8gdGhlIGxlZnQsIG9yIHRvIHRoZSByaWdodCBvZiBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBjZWxsIGhhcyBhIHBvc2l0aXZlIGludGVnZXIgdmFsdWUgYXNzb2NpYXRlZCB3aXRoIGl0LCBzcGVjaWZ5aW5nIGhvdyBhbXVzaW5nIHRoYXQgY2VsbCBpcyB0byB2aXNpdG9ycy4gVGhlIHRvdGFsIGFtdXNlbWVudCB2YWx1ZSBvZiB0aGUgY29hc3RlciBpcyB0aGUgc3VtIG9mIGFtdXNlbWVudCB2YWx1ZXMgb2YgYWxsIGNlbGxzIHRoYXQgdGhlIGNvYXN0ZXIgdmlzaXRzLiBIZWxwIE1pcmtvIGRldGVybWluZSBhbnkgb25lIG9mIHRoZSBtb3N0IGFtdXNpbmcgY29hc3RlcnMgKG9uZXMgd2l0aCB0aGUgbWF4aW11bSBzdW0pLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIFIgYW5kIEMgKDIgJmxlOyBSLCBDICZsZTsgMTAwMCksIHRoZSBkaW1lbnNpb25zIG9mIHRoZSB0YWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBSIGxpbmVzIGNvbnRhaW5zIEMgcG9zaXRpdmUgaW50ZWdlcnMgc21hbGxlciB0aGFuIDEwMDAsIHNwZWNpZnlpbmcgdGhlIGFtdXNlbWVudCB2YWx1ZXMgb2YgdGhlIHJlc3BlY3RpdmUgdGFibGUgY2VsbHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiBhIHNlcXVlbmNlIG9mIGxldHRlcnMgd2l0aCBubyBibGFua3MuIFRoZSBsZXR0ZXJzIHNwZWNpZnkgdGhlIHNlcXVlbmNlIG9mIGRpcmVjdGlvbnMgdGhhdCB0aGUgY29hc3RlciBmb2xsb3dzLCBzdGFydGluZyBmcm9tIHRoZSB1cHBlciBsZWZ0IGFuZCBlbmRpbmcgYXQgdGhlIGxvd2VyIHJpZ2h0IGNvcm5lci4gVGhlIGRpcmVjdGlvbnMgdXAsIHJpZ2h0LCBkb3duLCBsZWZ0IGFyZSBtYXJrZWQgYnkgbGV0dGVycyAmbHNxdW87VSZyc3F1bzssICZsc3F1bztSJnJzcXVvOywgJmxzcXVvO0QmcnNxdW87LCAmbHNxdW87TCZyc3F1bzssIHJlc3BlY3RpdmVseS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhlIHNvbHV0aW9uIGlzbiZyc3F1bzt0IGd1YXJhbnRlZWQgdG8gYmUgdW5pcXVlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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