[BOJ 1577] 도로의 개수

- 문제 요약

 

세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다. (0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오.

(세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다.)

 

 

- 알고리즘 정리

 

공사중인 도로는 배열에 따로 넣어서 체크해주고, 아래 점화식을 이용해서 문제를 해결해 주면 됩니다.

 

dp[i][j] : (0,0)부터 (i,j)까지 가는 서로 다른 경우의 수

dp[i][j] = dp[i-1][j] + dp[i][j-1]

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 105
typedef long long ll;
int n,m,k;
int dx[]={-1,0};
int dy[]={0,-1};
ll dp[MAX][MAX];
int arr[205][205];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>k;
	dp[0][0]=1;
	for(int i=0;i<k;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		arr[b+d][a+c]=1;
	}
	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++){
			for(int kk=0;kk<2;kk++){
				int nx=j+dx[kk];
				int ny=i+dy[kk];
				if(nx>=0 && nx<=n && ny>=0 && ny<=m){
					if(arr[ny+i][nx+j]!=1){
						dp[i][j]+=dp[ny][nx];
					}
				}
			}
		}
	}
	cout<<dp[m][n];
}

코드 제출 결과