BEAKJOON / 백준 - JAVA 14494번 다이나믹이 뭐예요?

2024.08.30기준 - 실버3

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

🟥 풀이

이 문제는 출발점 (1, 1)에서 도착점 (n, m)까지 갈 때, 주어진 세 방향으로 갔을 시 나오는 경우의 수를 출력하는 문제입니다.

 

접근 방법

1. 우선 문제에 나와있는 dp를 통해 접근을 시도했습니다.
2. 1000000007로 나눈 나머지의 경우의 수를 구하는 것이기 때문에 int를 이용해서 풀 수 있다고 생각을 했습니다.

 

1. dp를 저장할 배열을 생성해 x = 0일 때와 y = 0일 때를 미리 작업을 했습니다.

// 경우의수를 저장할 배열
int[][] numberCase = new int[y][x];

// x = 0일 때는 무조건 1가지의 방법 밖에 없다.
for (int i = 0; i < y; i++) {
    numberCase[i][0] = 1;
}

// y = 0일 때는 무조건 1가지의 방법 밖에 없다.
for (int i = 0; i < x; i++) {
    numberCase[0][i] = 1;
}

• 미리 하지 않아도 조건문을 통해 참조하는 범위를 제한하면 없어도 되는 코드가 됩니다.

2. 현재 좌표에서 참조할 좌표로 갈 배열들을 생성했습니다.

// 현재 좌표에서 참조할 위치
int[] dx = {-1, 0, -1};
int[] dy = {-1, -1, 0};

 

3. dp계산을 할 반복문을 생성해 마지막에 있는 좌표의 경우의 수를 구해줍니다.

// dp
for (int i = 1; i < y; i++) {
    for (int j = 1; j < x; j++) {
        for (int k = 0; k < 3; k++) {
            numberCase[i][j] += numberCase[i + dy[k]][j + dx[k]];

            // 너무 큰 수 가 들어오면 나머지를 구한다.
            if (numberCase[i][j] > 1000000007) {
                numberCase[i][j] %= 1000000007;
            }
        }
    }
}

 

 

🟪 코드

package Main;

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int y = Integer.parseInt(st.nextToken()); // 다차원배열의 세로 길이
		int x = Integer.parseInt(st.nextToken()); // 다차원배열의 가로 길이
		
		// 경우의수를 저장할 배열
		int[][] numberCase = new int[y][x];
		
		// x = 0일 때는 무조건 1가지의 방법 밖에 없다.
		for (int i = 0; i < y; i++) {
			numberCase[i][0] = 1;
		}
		
		// y = 0일 때는 무조건 1가지의 방법 밖에 없다.
		for (int i = 0; i < x; i++) {
			numberCase[0][i] = 1;
		}
		
		// 현재 좌표에서 참조할 위치
		int[] dx = {-1, 0, -1};
		int[] dy = {-1, -1, 0};
		
		// dp
		for (int i = 1; i < y; i++) {
			for (int j = 1; j < x; j++) {
				for (int k = 0; k < 3; k++) {
					numberCase[i][j] += numberCase[i + dy[k]][j + dx[k]];
					
					// 너무 큰 수 가 들어오면 나머지를 구한다.
					if (numberCase[i][j] > 1000000007) {
						numberCase[i][j] %= 1000000007;
					}
				}
			}
		}
		
		// 도착지점의 경우의 수를 출력
		int count = numberCase[y - 1][x - 1];
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
}