이번에 풀어본 문제는
백준 10164번 격자상의 경로 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int [][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        map = new int[N + 1][M + 1];

        map[0][1] = 1;

        int cnt = 0;
        boolean isCircle = false;
        int x = 0, y = 0;
        loop : for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                cnt++;
                map[i][j] = map[i - 1][j] + map[i][j - 1];
                if (cnt == K) {
                    isCircle = true;
                    x = i;
                    y = j;
                    break loop;
                }
            }
        }

        // 원이 존재한다면
        if (isCircle) {
            for (int i = x; i <= N; i++) {
                for (int j = y; j <= M; j++) {
                    if ((i - 1) >= x) map[i][j] += map[i - 1][j];
                    if ((j - 1) >= y) map[i][j] += map[i][j - 1];
                }
            }
        }
        System.out.print(map[N][M]);
    }
}

📝 풀이

주어진 두 가지 조건을 충족하여 N,M 까지 도달할 수 있는 경로의 개수를 출력하는 문제입니다.
map[i][j]까지의 경로는 map[i-1][j] + map[i][j-1]이라는 점을 활용하여 해결할 수 있습니다.
O가 그려진 인덱스를 무조건 포함해야하는 조건이 있기 때문에, O가 존재한다면, O를 거치지 않은 경로를 제외할 수 있는 조건을 추가하여 반복문을 다시 설계해주면 해결할 수 있습니다.
자세한 방법은 코드에 포함되어 있습니다.