백준 10164 격자상의 경로

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

10164번: 격자상의 경로

정답률은 30%대이지만 그렇게 어렵지 않은 문제였습니다. 중,고등학교 때 격자 길찾기 문제랑 똑같은 문제입니다.

시작점에서 가로 세로로 1을 모두 그리고 위, 왼쪽에 있는 값을 더해나가는 원리로 똑같이 하면 됩니다.

 

공식을 이용한 방법도 있습니다.

a가 n개, b가 m개, c가 k개, ...., 이런 식으로 있다고 하면 얘네를 나열할 수 있는 경우의 수는

(n+m+k+..)! / (n! m! k! ...) 입니다. 

해당 문제는 경우가 오른쪽, 아래쪽 2가지 방향만 있으므로 가로 세로 길이만 구하면 됩니다.

 

동그라미가 있는 경우는 해당 지점까지 위 공식으로 구하고 해당 지점부터 끝까지 위 공식으로 구한 뒤 둘을 곱하면 됩니다. (격자에 숫자 적을 때 동그라미 위치부터는 1 대신 동그라미의 값으로 적는 거랑 동일한 원리)

 

코드는 다음과 같습니다. (dp)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N, M, K;
int r, c; // 동그라미 위치, (1,1)부터 시작
int path[16][16];

void init()
{
	cin >> N >> M >> K;
	memset(path, 0, sizeof(path));

	if (K != 0) {
		r = K / M + 1;
		c = K % M;

		if (c == 0) {
			r -= 1;
			c = M;
		}
	}
	else {
		r = 0;
		c = 0;
	}

	// 시작부분 1로 채우기
	for (int i = 1; i <= N; i++) {
		path[i][1] = 1;
	}
	for (int i = 1; i <= M; i++) {
		path[1][i] = 1;
	}
}

// 격자점 길찾기와 동일한 문제
// 동그라미는 반드시 거쳐가는 곳
// 동그라미 있으면 1,1부터 동그라미까지 길찾기
// 동그라미부터 N,M 까지 길찾기 다시 시작
// 동그라미 없으면 1,1부터 N,M까지 길찾기

// 동그라미 없는 경우
int dp1(int n, int m)
{
	if (n == 1 || m == 1) {
		return 1;
	}

	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= m; j++) {
			path[i][j] = path[i - 1][j] + path[i][j - 1];
		}
	}

	return path[n][m];
}

// 동그라미 있는 경우
int dp2(int n, int m, int r, int c)
{
	if (n == 1 || m == 1)
		return 1;

	for (int i = 2; i <= r; i++) {
		for (int j = 2; j <= c; j++) {
			path[i][j] = path[i - 1][j] + path[i][j - 1];
		}
	}

	for (int i = r; i <= n; i++) {
		path[i][c] = path[r][c];
	}
	for (int i = c; i <= m; i++) {
		path[r][i] = path[r][c];
	}

	for (int i = r + 1; i <= n; i++) {
		for (int j = c + 1; j <= m; j++) {
			path[i][j] = path[i - 1][j] + path[i][j - 1];
		}
	}

	return path[n][m];
}

int main()
{
	init();
	if (r == 0 && c == 0) {
		cout << dp1(N, M);
	}
	else {
		cout << dp2(N, M, r, c);
	}
}

 

공식 (팩토리얼 처리하기 귀찮아서 파이썬으로 했습니다 ㅎㅎㅎ)

import math

def calculate(sx,sy,ex,ey):
    # sx,sy : start x,y
    # ex,ey : end x,y
    r = ey-sy
    c = ex-sx
    
    bunmo1 = math.factorial(r)
    bunmo2 = math.factorial(c)
    bunja = math.factorial(r+c)
    
    return int(bunja / (bunmo1 * bunmo2))
    
n,m,k = map(int,input().split())
result = 0

if k == 0:
    result = calculate(1,1,m,n)
    print(result)

else:
    cx = k % m
    cy = k // m + 1
    
    if cx == 0:
        cy -= 1
        cx = m
    
    result1 = calculate(1,1,cx,cy)
    result2 = calculate(cx,cy,m,n)
    result = result1 * result2
    print(result)