[BOJ 15924] 욱제는 사과팬이야!!

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

15924번: 욱제는 사과팬이야!!

 

- 문제 요약

 

지도의 가로, 세로 크기인 N, M과 도착지 X를 포함한 지도가 주어진다.

지도는 E(i, j+1로 이동), S(i+1, j로 이동), B(i+1, j 또는 i, j+1로 이동)로만 이루어져 있다.

욱제가 도착지 X에 선물을 놓을 때 구사과가 선물을 가져가는 경로의 수를 구하시오.

이때, 경로의 수는 1,000,000,009로 나눈 나머지를 출력하시오.

 

 

- 알고리즘 정리

 

우선 경로의 수를 구하라고 하는 것과 문제의 형식을 보니 DP 문제인 것 같습니다.

E는 오른쪽, S는 아래쪽, B는 오른쪽 or 아래쪽으로 간다는 걸 생각해서 2차원 DP 배열을 만들어주면 될 것 같습니다.

 

dp[i][j]가 (n-1, m-1)(도착지 X)에서 (1, 1)까지 가는 경우의 수라고 생각하겠습니다.

 

우선 if로 현재 인덱스가 도착지 X인지 아닌지 거르고, 아니라면 E, S, B 중 어떤 건지 판별을 합니다.

E인 경우에 점화식은 dp[i][j]=dp[i][j+1]이 될 테고, S인 경우에는 dp[i][j]=dp[i+1][j]이 될 것입니다.

B의 경우에는 오른쪽 또는 아래쪽으로 가니 dp[i][j]=dp[i+1][j]+dp[i][j+1]이 될 것입니다.

 

하지만 여기서 조심해야 할 부분이 있습니다.

 

경로의 수를 1,000,000,009로 나눈 나머지를 출력하라고 나와있는데, 경로를 다 구하고 나서 나누면 범위가 넘치는 경우도 있기에 점화식 연산을 할 때마다 나눠주는 것이 좋습니다.

1,000,000,009는 mm이라는 변수에 넣어 연산하겠습니다.

 

그러므로 E의 점화식은 dp[i][j]=dp[i][j+1]%mm, S의 점화식은 dp[i][j]=dp[i+1][j]%mm이 됩니다.

B의 점화식은 총 3번을 나눠줘야 하기 때문에 dp[i][j]=(dp[i+1][j]%mm+dp[i][j+1]%mm)%mm이 됩니다.

 

 

- 코드 작성

 

경로의 총합을 구하기 위해 num 변수를 사용했습니다.

#include<cstdio>
#include<iostream>
using namespace std;

int n,m,dp[3001][3001],mm=1000000009,num;
char arr[3001][3001];

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>arr[i][j];
		}
	}//입력 
	//S는 아래, E는 오른쪽, B는 아래, 오른쪽
	
	dp[n-1][m-1]=1;//뒤에서부터 시작 예정 
	
	for(int i=n-1;i>=0;i--){
		for(int j=m-1;j>=0;j--){
			if(i==n-1&&j==m-1){
				continue;
			}
			if(arr[i][j]=='S'){
				dp[i][j]=dp[i+1][j]%mm;	
			}
			if(arr[i][j]=='E'){
				dp[i][j]=dp[i][j+1]%mm;	
			}
			if(arr[i][j]=='B'){
				dp[i][j]=(dp[i+1][j]%mm+dp[i][j+1]%mm)%mm;
			}	
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			num+=dp[i][j]%mm;
			num%=mm;
		}
	} 
	cout<<num;
}

코드 제출 결과

항상 느끼는 거지만 DP 문제는 DP 배열 뜻 정의가 가장 힘든 것 같습니다.

그래도 구현은 간단하게 할 수 있어서 좋지만 그만큼 머리가 고통받는다는 사실...

 

덕분에 한 번 틀려버렸습니다 ㅎ