https://www.acmicpc.net/problem/10164
10164번: 격자상의 경로
입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으��
www.acmicpc.net
재귀함수로 적당히 풀었다.
#include<stdio.h>
int f(int x,int y, int px, int py){
if(x == px && y == py) return 1;
if(x > px || y > py) return 0;
return f(x+1,y,px,py) + f(x,y+1,px,py);
}
int main(){
int n,m,k;
scanf("%d %d %d", &n, &m, &k);
if(k==0) printf("%d", f(1,1,n,m));
else{
int h=(k-1)/m;
int w=(k-1)%m;
printf("%d", f(1,1,h+1,w+1)*f(h+1,w+1,n,m));
}
return 0;
}함수 f는 (x,y)에서 (px,py)로 가는 경우의 수를 구해준다.
아래거나 오른쪽으로밖에 못가므로 f(x+1,y...)과 f(x,y+1...)을 호출해서 아래로가거나 오른쪽으로가거나 두가지를 다 합산한다.
main함수에서는 입력받고
k가 0인경우(1,1)부터 (n,m)까지의 경우의 수를 구해서 출력해주면 되게끔 빼놨고
k가 0이 아닌 경우에는 중간점인 (h,w)를 구해서 (1,1)에서 (h+1,w+1)까지 구하고,
(h+1,w+1)에서 (n,m)까지를 구해서 곱해서 출력해주면 끝.
반응형