[C/C++ 백준 10164번] 격자상의 경로 (Silver 1)

https://www.acmicpc.net/problem/10164

10164번: 격자상의 경로

길찾기좀 해봤다, 하면은 쉽게 풀 수 있는 문제. dp[i][j]는 1,1 에서 i, j까지 갈 수 있는 경우의 수라 하면, 당연히 dp[i][j] += dp[i-1][j]+dp[i][j-1]; 이다.

 

ⓛ Circle 없는 경우 - 그냥 dp[N][M]

② Circle 있는 경우 - Circle의 좌표 Cx, Cy를 구한뒤, dp[Cx][Cy]*dp[N-Cx+1][M-Cy+1]를 하면 된다. N-Cx+1, M-Cy+1에서 초기값 dp[Cx][Cy]를 구한다는 느낌으로 하면 편하다. 실제로도 그렇고.

 

#include <cstdio>
int main(void){
	int N, M, K, Cx, Cy, cnt=0;
	scanf("%d %d %d",&N, &M, &K);
	long long int dp[16][16]={};
	dp[1][1]=1;
	for(int i=1; i<=N; i++)
		for(int j=1; j<=M; j++){
			dp[i][j] += dp[i-1][j]+dp[i][j-1];
	}
	if(K!=0){
		if(K%M!=0){
			Cy=K%M;
			Cx=(K-Cy)/M+1;
		}
		else{
			Cx=K/M;
			Cy=M;
		}
	}
	if(K==0)	printf("%lld",dp[N][M]);
	else	printf("%lld",dp[Cx][Cy]*dp[N-Cx+1][M-Cy+1]);
}