제31회 한국정보올림피아드 전국본선 (2014.7.11) 중등부 문제 1

문제는 더블릿 옥상에 있는 koi_path2014입니다.

문제 사이트 주소입니다.

http://183.106.113.109/pool/koi_path2014/koi_path2014.php?pname=koi_path2014

행렬이 있을 때 K가 0이면 1행 1열부터 끝까지, K가 0이 아니면 K가 들어있는 행렬을 거쳐갈 수 있는 경우의 수를 구하는 문제입니다.

행렬에서 첫 위치부터 특정 위치까지, 특히 오른쪽 혹은 아래로만 움직일 수 있는 경우는 자주 나옵니다.

예로 보면 7의 위치로 갈 수 있는 경우의 수는 2의 위치까지 갈 수 있는 경우의 수 + 6의 위치까지 갈 수 있는 경우의 수입니다.  15는 10의 위치까지 갈 수 있는 경우의 수 + 14의 위치까지 갈 수 있는 경우의 수입니다.

이런식으로 K가 0일 때를 구하면 되고 K가 0이 아닐 때는 이 과정을 2번 거쳐서 서로의 경우의 수를 곱해주면 됩니다.  인덱스는 1부터 순서대로 놓여지므로 K의 행과 열을 구해 1행 1열부터 K까지 가는 경우의 수를 구하고 K부터 마지막 행렬까지 가는 경우의 수를 구해 곱해주면 됩니다.