시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 559 132 104 31.707%

문제

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+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTkxXHVjNWQwIFx1YzgxNVx1YzIxOCBOKDQgJmxlOyBOICZsZTsgMTAwKVx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxIDB+OVx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWMyMmJcdWM3OTAgblx1YWMxY1x1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNjdjXHVjYWJkIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4XHViODVjIFx1YzcwNFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM1ZDAgXHViOWRlXHVhYzhjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDI8c3VwPjYzPFwvc3VwPi0xXHViY2Y0XHViMmU0IFx1ZDA3NCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCZuYnNwOzEwMFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWIxMThcdWM5YzBcdWIyOTQgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2p1bXAoMikucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMxcHg7IGxpbmUtaGVpZ2h0OjEuNmVtOyB3aWR0aDo0ODlweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzM3MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikp1bXAgVGhlIEJvYXJkISIsImRlc2NyaXB0aW9uIjoiPHA+QW4gbiAmdGltZXM7IG4gZ2FtZSBib2FyZCBpcyBwb3B1bGF0ZWQgd2l0aCBpbnRlZ2Vycywgb25lIG5vbm5lZ2F0aXZlIGludGVnZXIgcGVyIHNxdWFyZS4gVGhlIGdvYWwgaXMgdG8ganVtcCBhbG9uZyBhbnkgbGVnaXRpbWF0ZSBwYXRoIGZyb20gdGhlIHVwcGVyIGxlZnQgY29ybmVyIHRvIHRoZSBsb3dlciByaWdodCBjb3JuZXIgb2YgdGhlIGJvYXJkLiBUaGUgaW50ZWdlciBpbiBhbnkgb25lIHNxdWFyZSBkaWN0YXRlcyBob3cgbGFyZ2UgYSBzdGVwIGF3YXkgZnJvbSB0aGF0IGxvY2F0aW9uIG11c3QgYmUuIElmIHRoZSBzdGVwIHNpemUgd291bGQgYWR2YW5jZSB0cmF2ZWwgb2ZmIHRoZSBnYW1lIGJvYXJkLCB0aGVuIGEgc3RlcCBpbiB0aGF0IHBhcnRpY3VsYXIgZGlyZWN0aW9uIGlzIGZvcmJpZGRlbi4gQWxsIHN0ZXBzIG11c3QgYmUgZWl0aGVyIHRvIHRoZSByaWdodCBvciB0b3dhcmQgdGhlIGJvdHRvbS4gTm90ZSB0aGF0IGEgMCBpcyBhIGRlYWQgZW5kIHdoaWNoIHByZXZlbnRzIGFueSBmdXJ0aGVyIHByb2dyZXNzLjxcL3A+XHJcblxyXG48cD5Db25zaWRlciB0aGUgNCAmdGltZXM7IDQgYm9hcmQgc2hvd24gaW4gRmlndXJlIDEsIHdoZXJlIHRoZSBzb2xpZCBjaXJjbGUgaWRlbnRpZmllcyB0aGUgc3RhcnQgcG9zaXRpb24gYW5kIHRoZSBkYXNoZWQgY2lyY2xlIGlkZW50aWZpZXMgdGhlIHRhcmdldC4gRmlndXJlIDIgc2hvd3MgdGhlIHRocmVlIGxlZ2l0aW1hdGUgcGF0aHMgZnJvbSB0aGUgc3RhcnQgdG8gdGhlIHRhcmdldCwgd2l0aCB0aGUgaXJyZWxldmFudCBudW1iZXJzIGluIGVhY2ggcmVtb3ZlZC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9qdW1wKDMpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0MHB4OyB3aWR0aDo0OTJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIGxlZ2l0aW1hdGUgcGF0aHMgZnJvbSB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgdG8gdGhlIGxvd2VyIHJpZ2h0IGNvcm5lci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBhIGZpcnN0IGxpbmUgd2l0aCBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIDQgJmxlOyBuICZsZTsgMTAwLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIHJvd3MgaW4gdGhpcyBib2FyZC4gVGhpcyBpcyBmb2xsb3dlZCBieSBuIHJvd3Mgb2YgZGF0YS4gRWFjaCByb3cgY29udGFpbnMgbiBpbnRlZ2VycywgZWFjaCBvbmUgZnJvbSB0aGUgcmFuZ2UgMCZoZWxsaXA7OS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBjb25zaXN0IG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGxlZ2l0aW1hdGUgcGF0aHMgZnJvbSB0aGUgdXBwZXIgbGVmdCBjb3JuZXIgdG8gdGhlIGxvd2VyIHJpZ2h0IGNvcm5lci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2006 6번

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