[코이] 격자상의 경로

문제 링크

https://www.codeup.kr/problem.php?id=4818 <-- CodeUp

http://koistudy.net/?mid=prob_page&NO=2314&SEARCH=0 <-- KOISTUDY

 

목차

1. 문제 접근 방법

2. DP

 

문제 접근 방법

n*m 크기의 격자판에서 k번째 칸을 무조건 지나가는 경우의 수를 구하는 문제이다.

 

처음 해야 할 것은? 제일 작은 경우부터 하나 하나 그려 보면서 접근해야 한다.

여기서부터 DP라는 것이 감이 오는데 첫번째 칸을 가는 방법은 1가지이다. 2번째 칸을 가는 방법도 1가지이다. 3번째 칸을 가는 경우의 수도? 1가지이다. 다음 열을 봐보자. 2번째 열의 첫번째 칸을 가는 방법은 1가지이다. 2열의 2번째를 가는 방법은 1열의 2번째 칸을 지나는 경우 하나와 2열의 첫번째 칸을 지나는 경우가 존재하여 총 2가지이다. 하나만 더 해 보자면, 2열의 3번째 칸을 가는 방법은 1열의 3번째칸을 경우햐는 경우와 2열의 2번째 칸을 경유하는 방법이 있다. 이 때, 2열의 2번째 칸을 경유하는 경우는 2가지 이므로 2열의 3번째 칸을 경유하는 경우는 3가지이다. 이것을 표로 나타내 보면,

 

1 1 1 . . .

1 2 3 . . .

. . .

위와 같이 나타낼 수 있다.

 

여기서 규칙을 찾아보면, 인접한 두 곳을 경유하는 경우의 수를 더한 것은 원하는 지점을 갈 수 있는 총 경우의 수가 된다.

이를 점화식으로 바꾸면?

 

1 (p == 1 || q == 1)

d[p][q] = d[p-1][q] + d[p][q-1]

 

이라는 점화식이 나온다.

 

여기까지 접근하였다면, k를 지나는 경우를 생각해 주어야 한다.

k가 0인 경우에는 굳이 k를 지나는 경우를 생각해 줄 필요가 없다. 왜냐하면 k = 0인 경우 맨 처음을 무조건 경유하는 경우를 구하라는 것인데... 처음은 무조건 지나게 되어있으므로 이 경우에는 그냥 처음부터 끝까지가는 최대 경우를 구해주면 된다.

 

하지만! k가 0이 아닌 경우에는 어떻게 해답을 구할지 생각을 해야 한다. 우선 k까지 가는 경우는 우리가 무조건 구해야 하므로 k까지 가는 경우를 구해준다. 그런 다음 k부터 끝까지 가는 경우를 구해주면? k를 거쳐서 갈 수 있는 경우의 수를 나누어서 구해준 것이다.

 

3 5 8 이라는 데이터를 예시로 들면...

1	1	1
1	2	3 ( k번째 칸! )	3	3
		3	6	9

위 표를 자세히 보면, k번째 칸을 지나기 전과 지난 후의 패턴이 똑같다는 것을 볼 수 있다. 비슷한 경우를 몇개 해 보면 k번째 칸에서부터 (1, 1) 까지의 경우의 수와 (n, m) 부터 k번째 칸까지의 경우의 수를 곱은  k번째 칸을 지나서 가는 최대 경우의 수가 되는 것을 알 수 있다. ( 약간의 확률과 통계 개념이 들어가는 느낌이 들지만, 관찰하다 보면 충분히 해결할 수 있는 문제이다. )

 

DP

source code

#include <cstdio>

int n, m, k, x, y, s, d[110][110];

int f(int p, int q)
{
  if(p == 1 || q == 1) return 1;
  return d[p][q] = f(p-1, q)+f(p, q-1);
}

int main()
{
  scanf("%d%d%d", &n, &m, &k);
  for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++){
      s += 1;
      d[i][j] = s;
      if(s == k) x = i, y = j;
    }

  if(!k) printf("%d", f(n, m));
  else printf("%d", f(x, y)*f(n-x+1, m-y+1));

  return 0;
}

 

위에서 없던 코드 설명! 입력 받을 때, k번째 칸의 위치를 x와 y에 저장!

후에 저장된 값을 기반으로 k번째 칸까지의 경우를 구하는데 사용!!