10164번: 격자상의 경로

2022.02.03

 

문제 출처:

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

 

문제 분석:

o 표시가 되있는 칸이 있으면 o 표시를 꼭 지나야 할때 N, M 칸에 도달 하는 경우의 수를 구하여라.

로봇이 오른쪽, 아래만 갈 수 있기 때문에 중,고등학교 때 보던 최단거리 문제와 푸는 방법이 같을것 같다.

 

arr[i][j] = arr[i-1][j] + arr[i][j-1]

다음과 같은 점화식을 따른다.

 

문제 해결:

다른부분은 점화식 그대로 코드를 짜면되지만

K, o를 치는 부분을 x, y좌표로 나타내야된다.

Y좌표는 K / M

X좌표는 K - K/M*M - 1

로 나타냈다.

 

하지만 위와 같은 방법은

K를 M으로 나눴을때 나머지가 0일때는 다른값이 나와 예외처리를 해준다.

Y = K / M - 1

X = M - 1

 

내 소스코드:

int N, M, K;

int arr[17][17];

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);

   cin >> N >> M >> K;

   rep(i, N)
   {
      rep(j, M)
      {
         arr[i][j] = 1;
      }
   }
   int kY = 0;
   int kX = 0;

   if (K != 0)
   {
      kY = K / M;
      kX = K - K / M * M - 1;

      if (K % M == 0)
      {
         kY = K / M - 1;
         kX = M - 1;
      }
   }

   if (K == 0)
   {
      for (int i = 1; i < N; i++)
      {
         for (int j = 1; j < M; j++)
         {
            arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
         }
      }
   }
   else
   {
      for (int i = 1; i <= kY; i++)
      {
         for (int j = 1; j <= kX; j++)
         {
            arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
         }
      }

      int tmp = arr[kY][kX];

      for (int i = kY; i < N; i++)
      {
         arr[i][kX] = tmp;
      }
      for (int i = kX; i < M; i++)
      {
         arr[kY][i] = tmp;
      }

      for (int i = kY + 1; i < N; i++)
      {
         for (int j = kX + 1; j < M; j++)
         {
            arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
         }
      }
   }

   cout << arr[N - 1][M - 1];

   return 0;
}

고찰: 

최단거리 문제와 비슷하다고 생각해서 쉽게 접근 할 수 있었다.