BOJ - 10164 ) 격자상의 경로

 

---

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

10164번: 격자상의 경로

---

두가지 경우로 나누어 생각할 수있다.

 

격자상의 경로에서 중간점이 1)있는경우, 2)없는경우

 

없는 경우는 갈수있는 격자의 모든 경우의 수는

 

11111

12345

1361015

 

이런식으로 고등학교 수학에 나오는 방식으로 구할 수 있다.

 

dp[n][m] = dp[n-1][m] + dp[n][m-1]

 

카카오 1차 코테랑 비슷했던거 같다.

 

중간점이 있는경우에는

 

중간점을 기준으로 왼쪽위 오른쪽아래 2가지의 경우의수를 곱해주는 것으로 구할 수 있다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    
    public static int compute(int end_x , int end_y) {
        
        int map[][] = new int[end_y+1][end_x+1];
        
        for(int index = 0 ; index < end_x+1 ; index++) map[0][index] =1;
        for(int index = 0 ; index < end_y+1 ; index++) map[index][0] =1;
        
        for(int y = 1; y <end_y+1 ; y++) {
            for( int x = 1 ; x < end_x+1 ; x++) {
                map[y][x] = map[y-1][x] + map[y][x-1];
            }
        }
        
        return map[end_y][end_x];
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String arg = br.readLine();
        String arg_[] = arg.split(" ");
        int N = Integer.parseInt(arg_[0]); 
        int M = Integer.parseInt(arg_[1]); 
        int K = Integer.parseInt(arg_[2]); 
        if(K == 0) {
            System.out.println(compute(N-1,M-1));
        }
        else {
            int x =K%M-1;
            if(x <0) x = M-1;
            int y = K/M;
            if(K%M ==0) y--;
            System.out.println(compute(x,y) * compute(M-x-1,N-y-1));
        }
        
    }
 
}
 

---

결과는!!

 

당연히 맞았다.