[BOJ 백준] 출근 경로(5569) C++, Java

 

링크 : https://www.acmicpc.net/problem/5569

5569번: 출근 경로

 

문제 설명 : 

상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 

남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대로 번호가 1, 2, ..., h로 매겨져 있다. 서쪽에서 i번째 남북 방향 도로와 남쪽에서 j번째 동서 방향 도로가 만나는 교차로는 (i, j)이다.

상근이는 교차로 (1, 1)에 살고 있고, 교차로 (w, h)에 있는 회사에 차로 다니고 있다. 차는 도로로만 이동할 수 있다. 상근이는 회사에 최대한 빨리 가기 위해서, 동쪽 또는 북쪽으로만 이동할 수 있다. 또, 이 도시는 교통 사고를 줄이기 위해서 교차로를 돈 차량은 그 다음 교차로에서 다시 방향을 바꿀 수 없다. 즉, 교차로에서 방향을 바꾼 후, 1 블록만 이동한 후 다시 방향을 바꿀 수 없다.

상근이가 회사에 출근할 수 있는 경로의 수는 몇 가지 일까?

w와 h가 주어졌을 때, 가능한 출근 경로의 개수를 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 w와 h가 주어진다. (2 ≤ w, h ≤ 100)

출력 : 

첫째 줄에 상근이가 출근할 수 있는 경로의 개수를 100000로 나눈 나머지를 출력한다.

 

예제 입력 : 

15 15

예제 출력 : 

43688

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 사전 1256
public class Main {

	static int w, h, ans;
	
	// 출력용 변수
	static StringBuilder sb = new StringBuilder();

	static final int MAX_SIZE = 100+2;
	static final int MOD_NUMBER = 100000;

	// 방향을 연속해서 꺾을 수 없다 => 경우의 수를 나눠서 점화식 작성 (점프 문제)
	//   dp[ i ] [ j ][ 2 ][ 2 ]  :  { i, j } 좌표까지 오는 방법의 수
	//   dp[ i ] [ j ][ 0 ][ 0 ]  :   동쪽으로 → / 안 꺾음
	//   dp[ i ] [ j ][ 0 ][ 1 ]  :   동쪽으로 → / 꺾음
	//   dp[ i ] [ j ][ 1 ][ 0 ]  :   북쪽으로 ↑ / 안 꺾음
	//   dp[ i ] [ j ][ 1 ][ 1 ]  :   북쪽으로 ↑ / 꺾음
	static int[][][][] dp = new int [MAX_SIZE][MAX_SIZE][2][2];

	public static void main(String[] args) throws IOException {
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		
		w = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		
		// 2. dp 진행
		// 1) 파스칼 삼각형 1 깔고 시작 
		//   dp[ i ] [ j ][ 0 ][ 0 ]  :   동쪽으로 → / 안 꺾음
		for (int i = 1; i <= w; i++) {	// i / w 가로 너비
			dp[i][1][0][0] = 1;
		}
		//   dp[ i ] [ j ][ 1 ][ 0 ]  :   북쪽으로 ↑ / 안 꺾음
		for (int i = 1; i <= h; i++) {	// h 높이
			dp[1][i][1][0] = 1;
		}

		// 2) 점화식 수행
		//   i  / w idth 가로 진행   
		//   j  / h eight 세로 진행
		for (int i = 2; i <= w; i++) {
			for (int j = 2; j <= h; j++) {
				// 1) [ 0 ][ 0 ]  :   동쪽으로 → / 안 꺾음
				dp[i][j][0][0] = (dp[i-1][j][0][0] + dp[i-1][j][0][1])%MOD_NUMBER;

				// 2) [0][1] : 동쪽으로 → / 꺾음
				dp[i][j][0][1] = dp[i-1][j][1][0]%MOD_NUMBER;     // ↑(안꺾) +  →(꺾) 조합

				// 3) [1][0] : 북쪽으로 ↑ / 안 꺾음
				dp[i][j][1][0] = (dp[i][j-1][1][1] + dp[i][j-1][1][0])%MOD_NUMBER;

				// 4) [1][1] : 북쪽으로 ↑ / 꺾음
				dp[i][j][1][1] = dp[i][j-1][0][0] % MOD_NUMBER;   // →(안꺾)  + ↑ (꺾) 조합
			}
		}
		ans = (dp[w][h][0][0] + dp[w][h][0][1] + dp[w][h][1][0] + dp[w][h][1][1]) % MOD_NUMBER;


		// 4. 출력
		System.out.println(ans);
		br.close();
	}
}

 

C++ 코드 : 

// 출근경로 5569
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (100+2)
#define MOD (100000)

using namespace std;

int w, h;
int ans;

// 방향을 연속해서 꺾을 수 없다 => 경우의 수를 나눠서 점화식 작성 (점프 문제)
//   dp[ i ] [ j ][ 2 ][ 2 ]  :  { i, j } 좌표까지 오는 방법의 수
//   dp[ i ] [ j ][ 0 ][ 0 ]  :   동쪽으로 → / 안 꺾음
//   dp[ i ] [ j ][ 0 ][ 1 ]  :   동쪽으로 → / 꺾음
//   dp[ i ] [ j ][ 1 ][ 0 ]  :   북쪽으로 ↑ / 안 꺾음
//   dp[ i ] [ j ][ 1 ][ 1 ]  :   북쪽으로 ↑ / 꺾음
int dp[MAX][MAX][2][2];

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &w, &h);

	// 2. DP 진행
	// 1) 파스칼 삼각형 1 깔고 시작 
	//   dp[ i ] [ j ][ 0 ][ 0 ]  :   동쪽으로 → / 안 꺾음
	for (int i = 1; i <= w; i++) {	// i / w 가로 너비
		dp[i][1][0][0] = 1;
	}
	//   dp[ i ] [ j ][ 1 ][ 0 ]  :   북쪽으로 ↑ / 안 꺾음
	for (int i = 1; i <= h; i++) {	// h 높이
		dp[1][i][1][0] = 1;
	}

	// 2) 점화식 수행
	//   i  / w idth 가로 진행   
	//   j  / h eight 세로 진행
	for (int i = 2; i <= w; i++) {
		for (int j = 2; j <= h; j++) {
			// 1) [ 0 ][ 0 ]  :   동쪽으로 → / 안 꺾음
			               //     →
			dp[i][j][0][0] = (dp[i-1][j][0][0] + dp[i-1][j][0][1])%MOD;

			// 2) [0][1] : 동쪽으로 → / 꺾음
			dp[i][j][0][1] = dp[i-1][j][1][0]%MOD;     // ↑(안꺾) +  →(꺾) 조합

			// 3) [1][0] : 북쪽으로 ↑ / 안 꺾음
			dp[i][j][1][0] = (dp[i][j-1][1][1] + dp[i][j-1][1][0])%MOD;

			// 4) [1][1] : 북쪽으로 ↑ / 꺾음
			dp[i][j][1][1] = dp[i][j-1][0][0] % MOD;   // →(안꺾)  + ↑ (꺾) 조합
		}
	}
	ans = (dp[w][h][0][0] + dp[w][h][0][1] + dp[w][h][1][0] + dp[w][h][1][1]) % MOD;

	// 3. 출력
	printf("%d", ans);

	return 0;
}
#endif