시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1420 399 292 29.979%

문제

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

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

이 부지는 직사각형 모양이고, 상근이는 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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFlMzBcdWMwNjhcdWM3NDQgXHVjOGZjXHViMjk0IFx1Yjg2NFx1YjdlY1x1Y2Y1NFx1YzJhNFx1ZDEzMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YzcwNCBcdWNlNzhcdWJkODBcdWQxMzAgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjZTc4XHVjNzNjXHViODVjIFx1YzViNFx1YjViYlx1YWM4YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzQgXHViNDE4XHViMjk0XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzA0XHViMjk0IFUsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBSLCBcdWM2N2NcdWNhYmRcdWM3NDAgTCwgXHVjNTQ0XHViNzk4XHViMjk0IERcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWM3N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODczIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTFVOQVBBUksiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyBncm93biB0aXJlZCBvZiBhbGwgdGhlIGJvb2tzLCBzbyBoZSBkZWNpZGVkIHRvIGdvIHRvIHRoZSBhbXVzZW1lbnQgcGFyayB3aXRoIGhpcyBmcmllbmRzLCBkZXNwaXRlIG5vdCBsaWtpbmcgcm9sbGVyIGNvYXN0ZXJzLiBXaGlsZSBoaXMgZnJpZW5kcyBhcmUgaGF2aW5nIHRoZSB0aW1lIG9mIHRoZWlyIGxpdmVzIHJpZGluZyB0aGUgY29hc3RlcnMsIE1pcmtvIGlzIHNpdHRpbmcgb24gYSBiZW5jaCwgd2FpdGluZyBhbmQgdGhpbmtpbmcgYWJvdXQgdGhlIHBvc3NpYmxlIHBhdGhzIG9mIHRoZSBjb2FzdGVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGFtdXNlbWVudCBwYXJrJnJzcXVvO3MgYXJlYSBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSB0YWJsZSBvZiBSIHJvd3MgYnkgQyBjb2x1bW5zLiBBIHJvbGxlciBjb2FzdGVyIGhhcyB0byBzdGFydCBmcm9tIHRoZSB1cHBlciBsZWZ0IGNvcm5lciBhbmQgZW5kIGF0IHRoZSBsb3dlciByaWdodCBjb3JuZXIgb2YgdGhlIHRhYmxlLiBFYWNoIGNlbGwgY2FuIGJlIHZpc2l0ZWQgYXQgbW9zdCBvbmNlLCBidXQgbm90IGFsbCBjZWxscyBuZWVkIHRvIGJlIHZpc2l0ZWQuIEl0IGNhbiBjb250aW51ZSBpdHMgcGF0aCBmcm9tIHRoZSBjdXJyZW50IGNlbGwgdG8gdGhlIGFkamFjZW50IG9uZSBhYm92ZSwgYmVsb3csIHRvIHRoZSBsZWZ0LCBvciB0byB0aGUgcmlnaHQgb2YgaXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggY2VsbCBoYXMgYSBwb3NpdGl2ZSBpbnRlZ2VyIHZhbHVlIGFzc29jaWF0ZWQgd2l0aCBpdCwgc3BlY2lmeWluZyBob3cgYW11c2luZyB0aGF0IGNlbGwgaXMgdG8gdmlzaXRvcnMuIFRoZSB0b3RhbCBhbXVzZW1lbnQgdmFsdWUgb2YgdGhlIGNvYXN0ZXIgaXMgdGhlIHN1bSBvZiBhbXVzZW1lbnQgdmFsdWVzIG9mIGFsbCBjZWxscyB0aGF0IHRoZSBjb2FzdGVyIHZpc2l0cy4gSGVscCBNaXJrbyBkZXRlcm1pbmUgYW55IG9uZSBvZiB0aGUgbW9zdCBhbXVzaW5nIGNvYXN0ZXJzIChvbmVzIHdpdGggdGhlIG1heGltdW0gc3VtKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSIGFuZCBDICgyICZsZTsgUiwgQyAmbGU7IDEwMDApLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgdGFibGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgUiBsaW5lcyBjb250YWlucyBDIHBvc2l0aXZlIGludGVnZXJzIHNtYWxsZXIgdGhhbiAxMDAwLCBzcGVjaWZ5aW5nIHRoZSBhbXVzZW1lbnQgdmFsdWVzIG9mIHRoZSByZXNwZWN0aXZlIHRhYmxlIGNlbGxzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gYSBzZXF1ZW5jZSBvZiBsZXR0ZXJzIHdpdGggbm8gYmxhbmtzLiBUaGUgbGV0dGVycyBzcGVjaWZ5IHRoZSBzZXF1ZW5jZSBvZiBkaXJlY3Rpb25zIHRoYXQgdGhlIGNvYXN0ZXIgZm9sbG93cywgc3RhcnRpbmcgZnJvbSB0aGUgdXBwZXIgbGVmdCBhbmQgZW5kaW5nIGF0IHRoZSBsb3dlciByaWdodCBjb3JuZXIuIFRoZSBkaXJlY3Rpb25zIHVwLCByaWdodCwgZG93biwgbGVmdCBhcmUgbWFya2VkIGJ5IGxldHRlcnMgJmxzcXVvO1UmcnNxdW87LCAmbHNxdW87UiZyc3F1bzssICZsc3F1bztEJnJzcXVvOywgJmxzcXVvO0wmcnNxdW87LCByZXNwZWN0aXZlbHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IFRoZSBzb2x1dGlvbiBpc24mcnNxdW87dCBndWFyYW50ZWVkIHRvIGJlIHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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