시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB129634528332.641%

문제

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

힌트

그림 1 그림 2
W3sicHJvYmxlbV9pZCI6IjMzNzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWI0ZGMgXHVjODEwXHVkNTA0IiwiZGVzY3JpcHRpb24iOiI8cD5OICZ0aW1lczsgTiBcdWFjOGNcdWM3ODQgXHViY2Y0XHViNGRjXHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NzQgXHVjODAxXHVkNjAwXHVjNzg4XHViMmU0LiBcdWJhYTlcdWM4MDFcdWM3NDAgXHVjNjdjXHVjYWJkIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4XHVhZTRjXHVjOWMwIFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI5ZGVcdWFjOGMgXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU3NFx1YzExYyBcdWFjMDBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NDAgXHVkNjA0XHVjN2FjIFx1YzgxMFx1YzVkMFx1YzExYyBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzc0XHViMDk4IFx1YzU0NFx1Yjc5OFx1Y2FiZFx1YzczY1x1Yjg1Y1x1YjljYyBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCAwXHVjNzQwIFx1YjM1NCBcdWM3NzRcdWMwYzFcdWM3NTggXHVjOWM0XHVkNTg5XHVjNzQ0IFx1YjljOVx1YjI5NCBcdWM4ODVcdWNjMjlcdWM4MTBcdWM3NzRcdWIyZTQuIFx1YjJlNFx1YzJkYyBcdWI5ZDBcdWQ1NzRcdWMxMWMgXHVkNjA0XHVjN2FjIFx1YzgxMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5Y2NcdWQwN2MgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzc0XHViMDk4Jm5ic3A7XHVjNTQ0XHViNzk4XHVjYWJkXHVjNzNjXHViODVjIFx1YWMwMFx1YzU3Y1x1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1OTFcdWM1ZDAgXHVjODE1XHVjMjE4IE4oNCAmbGU7IE4gJmxlOyAxMDApXHVhYzAwIFx1YjRlNFx1YzViNFx1YzYyNFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDFcdWFjMDEgMH45XHVjMGFjXHVjNzc0XHVjNzU4IFx1YzIyYlx1Yzc5MCBOXHVhYzFjXHVhYzAwIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM2N2NcdWNhYmQgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OThcdWI4NWMgXHVjNzA0XHVjNzU4IFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI5ZGVcdWFjOGMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMjxzdXA+NjM8XC9zdXA+LTFcdWJjZjRcdWIyZTQgXHVkMDc0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsJm5ic3A7MTAwXHVjNzkwXHViOWFjXHViOTdjIFx1YjExOFx1YzljMFx1YjI5NCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6Ijx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkIHRkLWNlbnRlclwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNTYzZmJmZGEtNjc1MC00OWNhLTkzMWQtMTI1ZDQyNTljODcwXC8tXC9jcm9wXC8xOTV4MTkyXC8wLDBcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDk4cHg7IGhlaWdodDogOTZweDtcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNTYzZmJmZGEtNjc1MC00OWNhLTkzMWQtMTI1ZDQyNTljODcwXC8tXC9jcm9wXC82NDB4MTkyXC8zMDIsMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzIwcHg7IGhlaWdodDogOTZweDtcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHVhZGY4XHViOWJjIDE8XC90ZD5cclxuXHRcdFx0PHRkPlx1YWRmOFx1YjliYyAyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzM3MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikp1bXAgVGhlIEJvYXJkISIsImRlc2NyaXB0aW9uIjoiPHA+QW4gbiAmdGltZXM7IG4gZ2FtZSBib2FyZCBpcyBwb3B1bGF0ZWQgd2l0aCBpbnRlZ2Vycywgb25lIG5vbm5lZ2F0aXZlIGludGVnZXIgcGVyIHNxdWFyZS4gVGhlIGdvYWwgaXMgdG8ganVtcCBhbG9uZyBhbnkgbGVnaXRpbWF0ZSBwYXRoIGZyb20gdGhlIHVwcGVyIGxlZnQgY29ybmVyIHRvIHRoZSBsb3dlciByaWdodCBjb3JuZXIgb2YgdGhlIGJvYXJkLiBUaGUgaW50ZWdlciBpbiBhbnkgb25lIHNxdWFyZSBkaWN0YXRlcyBob3cgbGFyZ2UgYSBzdGVwIGF3YXkgZnJvbSB0aGF0IGxvY2F0aW9uIG11c3QgYmUuIElmIHRoZSBzdGVwIHNpemUgd291bGQgYWR2YW5jZSB0cmF2ZWwgb2ZmIHRoZSBnYW1lIGJvYXJkLCB0aGVuIGEgc3RlcCBpbiB0aGF0IHBhcnRpY3VsYXIgZGlyZWN0aW9uIGlzIGZvcmJpZGRlbi4gQWxsIHN0ZXBzIG11c3QgYmUgZWl0aGVyIHRvIHRoZSByaWdodCBvciB0b3dhcmQgdGhlIGJvdHRvbS4gTm90ZSB0aGF0IGEgMCBpcyBhIGRlYWQgZW5kIHdoaWNoIHByZXZlbnRzIGFueSBmdXJ0aGVyIHByb2dyZXNzLjxcL3A+XHJcblxyXG48cD5Db25zaWRlciB0aGUgNCAmdGltZXM7IDQgYm9hcmQgc2hvd24gaW4gRmlndXJlIDEsIHdoZXJlIHRoZSBzb2xpZCBjaXJjbGUgaWRlbnRpZmllcyB0aGUgc3RhcnQgcG9zaXRpb24gYW5kIHRoZSBkYXNoZWQgY2lyY2xlIGlkZW50aWZpZXMgdGhlIHRhcmdldC4gRmlndXJlIDIgc2hvd3MgdGhlIHRocmVlIGxlZ2l0aW1hdGUgcGF0aHMgZnJvbSB0aGUgc3RhcnQgdG8gdGhlIHRhcmdldCwgd2l0aCB0aGUgaXJyZWxldmFudCBudW1iZXJzIGluIGVhY2ggcmVtb3ZlZC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWQgdGQtY2VudGVyXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81NjNmYmZkYS02NzUwLTQ5Y2EtOTMxZC0xMjVkNDI1OWM4NzBcLy1cL2Nyb3BcLzE5NXgxOTJcLzAsMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogOThweDsgaGVpZ2h0OiA5NnB4O1wiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81NjNmYmZkYS02NzUwLTQ5Y2EtOTMxZC0xMjVkNDI1OWM4NzBcLy1cL2Nyb3BcLzY0MHgxOTJcLzMwMiwwXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAzMjBweDsgaGVpZ2h0OiA5NnB4O1wiIFwvPjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5GaWd1cmUgMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+RmlndXJlIDI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBudW1iZXIgb2YgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSB1cHBlciBsZWZ0IGNvcm5lciB0byB0aGUgbG93ZXIgcmlnaHQgY29ybmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGEgZmlyc3QgbGluZSB3aXRoIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbiwgNCAmbGU7IG4gJmxlOyAxMDAsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2Ygcm93cyBpbiB0aGlzIGJvYXJkLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IG4gcm93cyBvZiBkYXRhLiBFYWNoIHJvdyBjb250YWlucyBuIGludGVnZXJzLCBlYWNoIG9uZSBmcm9tIHRoZSByYW5nZSAwJmhlbGxpcDs5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnNpc3Qgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgbGVnaXRpbWF0ZSBwYXRocyBmcm9tIHRoZSB1cHBlciBsZWZ0IGNvcm5lciB0byB0aGUgbG93ZXIgcmlnaHQgY29ybmVyLjxcL3A+XHJcblxyXG48cD5JdCBpcyBndWFyYW50ZWVkIHRoYXQgYWxsIGlucHV0cyB3aWxsIGxlYWQgdG8gYSBudW1iZXIgb2YgbGVnaXRpbWF0ZSBwYXRocyB0aGF0IGNhbiBiZSB3cml0dGVuIHdpdGggbm8gbW9yZSB0aGFuIDEwMCBkaWdpdHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번

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