백준 10164 격자상의 경로(Java)

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

10164번: 격자상의 경로

---

 

해석 및 팁

 

---

 

이 문제는 k가 0일 때와 0이 아닐 때를 구분해서 풀어야 합니다. k가 0일 때는 조건 없이 경로의 수를 개산 해주면 되고 k가 0이 아닐 때는 k까지의 범위를 2개로 나누어서 곱해주면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();
    int k = sc.nextInt();
    int[][] arr = new int[n][m];

    if(k == 0) {
      for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
          if(i == 0 || j == 0) arr[i][j] = 1;
          else arr[i][j] = arr[i][j - 1] + arr[i - 1][j];
        }
      }
      System.out.println(arr[n - 1][m - 1]);
    }

    else {
      int midx = (k - 1) / m;
      int midy = (k - 1) % m;

      for(int i = 0; i <= midx; i++) {
        for(int j = 0; j <= midy; j++) {
          if(i == 0 || j == 0) arr[i][j] = 1;
          else arr[i][j] = arr[i][j - 1] + arr[i - 1][j];
        }
      }
      
      int a = arr[midx][midy];

      for(int i = midx; i < n; i++) {
        for(int j = midy; j < m; j++) {
          if(i == midx || j == midy) arr[i][j] = 1;
          else arr[i][j] = arr[i][j - 1] + arr[i - 1][j];
        }
      }

      int b = arr[n - 1][m - 1];
      System.out.println(a * b);
    }

  }
}