[백준] 10164번 : 격자상의 경로

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

10164번: 격자상의 경로

전에 비슷한 경로의 수 구하는 문제를 풀었던 기억이 있어서 DP로 금방 구현하였다.

 

이 문제에서 핵심은 O로 표시된 좌표를 꼭 지나가야된다는 것이다.

만약, 다음과 같은 사진에서 8을 꼭 지나야 한다면,

8을 기준으로 왼쪽 밑 & 오른쪽 위 좌표들은 계산할 필요도 없고 누적 경로수 계산에 포함시키면 안된다. (Check 함수로 구현하였다.)

전체코드는 아래와 같다!

#include <iostream>
using namespace std;

int N, M, K;
int dx[2] = { 0,-1 };//뒤,위
int dy[2] = { -1,0 };
int map[16][16];
int absX, absY;

bool check(int x, int y) {
	if (x > absX && y < absY) return false; //O기준 왼쪽밑
	else if (x<absX && y>absY) return false; //O기준 오른쪽위
	else return true;
}

int main() {
	cin >> N >> M >> K;
	if (K != 0) { //꼭 지나가야 하는곳의 좌표
		absX = (K % M == 0 ? K / M : K / M + 1); 
		absY = (K % M == 0 ? M : K % M);
	}
	map[1][1] = 1;
	for (int i = 1; i <=N ; i++){
		for (int j = 1; j <= M; j++) {
			if (i == 1 && j == 1) continue;
			if (K!=0 && !check(i, j)) continue; //거리 정보 사용여부
			for (int k = 0; k < 2; k++){ 
				int cx = i + dx[k];
				int cy = j + dy[k];
				if (cx >= 1 && cx <= N && cy >= 1 && cy <= M) map[i][j] += map[cx][cy]; //경우의 수 누적
			}
		}
	}
	cout << map[N][M]<<endl;
}