정보올림피아드 문제를 한번 풀어봅시다.

안녕하세요 두번째 포스팅 입니다.

오늘은 2014 정보올림피아드 전국대회 1번 문제를 풀어봅시다.

문제입니다.  1번 문제인 만큼 정말 쉽죠?

이 문제는 다이나믹프로그래밍을 사용하면 쉽게 해결이 가능 합니다.

와 다이나믹이라니 이름부터 참 다이나믹하죠?

코드 보시겠습니다.

#include <stdio.h> int path(int n, int m) { static int cache[20][20]; if (n == 1 || m == 1) return 1; if (cache[n][m] != 0) return cache[n][m]; else return cache[n][m] = path(n - 1, m) + path(n, m - 1); } int main(void) { int n, m; int target; int result; scanf("%d %d", &n, &m); scanf("%d", &target); if (target != 0) { int y, x; if (target % m == 0) { y = target / m; x = m; } else { y = target / m + 1; x = target % m; } result = path(y, x); result *= path(n - y + 1, m - x + 1); } else result = path(n, m); printf("%d \n", result); return 0; }

조금 길죠?  하지만 간단합니다.

path 함수를 먼저 봅시다.

기저사례는 보시듯이 n이 1이거나 m이 1일 때 입니다.

일단 cache라는 배열을 선언하여 저장소를 만들어줍니다.

그리고 만역 cache[n][m]에 데이터가 있다면 그 데이터를 반환합니다.

아니라면 cache[n][n]에 (n-1, m) 까지의 경로 수와 (n, m-1)경로 수를 더한 값을 저장하고 반환합니다.

메인 함수에서는 만약 target이 0일때 path함수를 한번만 호출하고

아니라면 두 번 호출합니다.

그러나 예외의 경우가 있는데요 target % m 이 0일때 입니다.

이 경우를 제외하면 그냥 저 대로 하면 됩니다.

1번은 쉽죠??

다같이 정올 대상을 위해 공부합시다.

여기까지~!