Informatica Online Judge

  격자길 [0246 / 00F6]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 241   Total Tried : 1060


The Champion of this Problem (C++) : gs17033 - ms / 188byte
My Best Submission (C++) : N/A

[]

Background

n×m 격자에서 왼쪽 위(0,0)에서 오른쪽 아래(n,m)까지 갈 수 있는 길의 수를 헤아리고자 한다.



길을 갈 때 몇 가지 제약사항이 있다.
(1) 격자 위의 선을 따라간다.
(2) 아래쪽 또는 오른쪽으로만 갈 수 있다.
(3) (0,0)과 (n,m)을 잇는 대각선보다 위쪽에 있는 점들은 통과할 수 없다. (대각선에 위치하는 점은 통과할 수 있다.) 아래의 그림에서 흰점은 통과할 수 없는 점이고 검은 점은 통과할 수 있는 점이다.



예를 들어, 3×4 격자에서 갈 수 있는 길은 다음과 같이 5가지가 있다.



격자의 크기가 입력되었을 때 (0,0)부터 (n,m)까지 갈 수 있는 길의 수를 출력하는 프로그램을 작성하시오.

Input

1. 두 개의 정수 n과 m이 입력된다.
2. n은 격자의 세로 크기를, m은 격자의 가로 크기를 각각 나타낸다.

[입력값의 정의역]
1 <= n, m <= 15

[Sub-Task Info]
#1 : max(n, m) <= 10
#2, #3 : max(n, m) <= 12
#4 : 추가 제한 조건 없음

Output

(0,0)에서 (n,m)까지 갈 수 있는 길의 수를 출력한다.

IO Example

입력
3 4

출력
5

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]