시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 542 125 99 31.429%

문제

n*n 게임 보드에 양의 숫자들이 적혀있다. 목적은 왼쪽 위에서 오른쪽 아래까지 규칙에 맞게 점프를 해서 가는 것이다. 숫자들은 현재 점에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 갈 수 있으며 0은 더 이상의 진행을 막는 종착점이다. 다시 말해서 현재 점의 숫자만큼 오른쪽이나 아래쪽으로 가야한다는 의미이다.

입력

첫번째 줄에는 양에 정수 N(4 ≤ N ≤ 100)가 들어오고, 그 다음 n개의 줄에 각각 0~9사이의 숫자 n개가 들어온다.

출력

왼쪽 위에서 오른쪽 아래로 위의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 클 수 있으며, 100자리를 넘지는 않는다.

예제 입력 1

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

예제 출력 1

3

힌트

W3sicHJvYmxlbV9pZCI6IjMzNzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWI0ZGMgXHVjODEwXHVkNTA0IiwiZGVzY3JpcHRpb24iOiI8cD5uKm4gXHVhYzhjXHVjNzg0IFx1YmNmNFx1YjRkY1x1YzVkMCBcdWM1OTFcdWM3NTggXHVjMjJiXHVjNzkwXHViNGU0XHVjNzc0IFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjJlNC4gXHViYWE5XHVjODAxXHVjNzQwIFx1YzY3Y1x1Y2FiZCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OFx1YWU0Y1x1YzljMCBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViOWRlXHVhYzhjIFx1YzgxMFx1ZDUwNFx1Yjk3YyBcdWQ1NzRcdWMxMWMgXHVhYzAwXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjMjJiXHVjNzkwXHViNGU0XHVjNzQwIFx1ZDYwNFx1YzdhYyBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzcwXHViOWFjXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHViYzE4XHViNGRjXHVjMmRjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc3NFx1YjA5OCBcdWM1NDRcdWI3OThcdWNhYmRcdWM3M2NcdWI4NWNcdWI5Y2MgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAgMFx1Yzc0MCBcdWIzNTQgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzljNFx1ZDU4OVx1Yzc0NCBcdWI5YzlcdWIyOTQgXHVjODg1XHVjYzI5XHVjODEwXHVjNzc0XHViMmU0LiBcdWIyZTRcdWMyZGMgXHViOWQwXHVkNTc0XHVjMTFjIFx1ZDYwNFx1YzdhYyBcdWM4MTBcdWM3NTggXHVjMjJiXHVjNzkwXHViOWNjXHVkMDdjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc3NFx1YjA5OCZuYnNwO1x1YzU0NFx1Yjc5OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM1N2NcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1OTFcdWM1ZDAgXHVjODE1XHVjMjE4IE4oNCAmbGU7IE4gJmxlOyAxMDApXHVhYzAwIFx1YjRlNFx1YzViNFx1YzYyNFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDEgMH45XHVjMGFjXHVjNzc0XHVjNzU4IFx1YzIyYlx1Yzc5MCBuXHVhYzFjXHVhYzAwIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM2N2NcdWNhYmQgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OThcdWI4NWMgXHVjNzA0XHVjNzU4IFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI5ZGVcdWFjOGMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMjxzdXA+NjM8XC9zdXA+LTFcdWJjZjRcdWIyZTQgXHVkMDc0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsJm5ic3A7MTAwXHVjNzkwXHViOWFjXHViOTdjIFx1YjExOFx1YzljMFx1YjI5NCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvanVtcCgyKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzFweDsgbGluZS1oZWlnaHQ6MS42ZW07IHdpZHRoOjQ4OXB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzcyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSnVtcCBUaGUgQm9hcmQhIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBuICZ0aW1lczsgbiBnYW1lIGJvYXJkIGlzIHBvcHVsYXRlZCB3aXRoIGludGVnZXJzLCBvbmUgbm9ubmVnYXRpdmUgaW50ZWdlciBwZXIgc3F1YXJlLiBUaGUgZ29hbCBpcyB0byBqdW1wIGFsb25nIGFueSBsZWdpdGltYXRlIHBhdGggZnJvbSB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgdG8gdGhlIGxvd2VyIHJpZ2h0IGNvcm5lciBvZiB0aGUgYm9hcmQuIFRoZSBpbnRlZ2VyIGluIGFueSBvbmUgc3F1YXJlIGRpY3RhdGVzIGhvdyBsYXJnZSBhIHN0ZXAgYXdheSBmcm9tIHRoYXQgbG9jYXRpb24gbXVzdCBiZS4gSWYgdGhlIHN0ZXAgc2l6ZSB3b3VsZCBhZHZhbmNlIHRyYXZlbCBvZmYgdGhlIGdhbWUgYm9hcmQsIHRoZW4gYSBzdGVwIGluIHRoYXQgcGFydGljdWxhciBkaXJlY3Rpb24gaXMgZm9yYmlkZGVuLiBBbGwgc3RlcHMgbXVzdCBiZSBlaXRoZXIgdG8gdGhlIHJpZ2h0IG9yIHRvd2FyZCB0aGUgYm90dG9tLiBOb3RlIHRoYXQgYSAwIGlzIGEgZGVhZCBlbmQgd2hpY2ggcHJldmVudHMgYW55IGZ1cnRoZXIgcHJvZ3Jlc3MuPFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoZSA0ICZ0aW1lczsgNCBib2FyZCBzaG93biBpbiBGaWd1cmUgMSwgd2hlcmUgdGhlIHNvbGlkIGNpcmNsZSBpZGVudGlmaWVzIHRoZSBzdGFydCBwb3NpdGlvbiBhbmQgdGhlIGRhc2hlZCBjaXJjbGUgaWRlbnRpZmllcyB0aGUgdGFyZ2V0LiBGaWd1cmUgMiBzaG93cyB0aGUgdGhyZWUgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSBzdGFydCB0byB0aGUgdGFyZ2V0LCB3aXRoIHRoZSBpcnJlbGV2YW50IG51bWJlcnMgaW4gZWFjaCByZW1vdmVkLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2p1bXAoMykucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQwcHg7IHdpZHRoOjQ5MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBudW1iZXIgb2YgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSB1cHBlciBsZWZ0IGNvcm5lciB0byB0aGUgbG93ZXIgcmlnaHQgY29ybmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGEgZmlyc3QgbGluZSB3aXRoIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbiwgNCAmbGU7IG4gJmxlOyAxMDAsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGlzIGJvYXJkLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IG4gcm93cyBvZiBkYXRhLiBFYWNoIHJvdyBjb250YWlucyBuIGludGVnZXJzLCBlYWNoIG9uZSBmcm9tIHRoZSByYW5nZSAwJmhlbGxpcDs5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnNpc3Qgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSB1cHBlciBsZWZ0IGNvcm5lciB0byB0aGUgbG93ZXIgcmlnaHQgY29ybmVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: conankun