아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

출근 경로

면접 대비

시간 제한1초메모리 제한128 MB

요약
서쪽 아래 (1,1)에서 동쪽 위 (w,h)로 동쪽과 북쪽으로만 이동하되, 연속한 교차로에서 방향을 두 번 바꾸지 않는 경로의 수를 100000으로 나눈 나머지를 구한다.
난이도

보통10점 중 5점

유형
동적 계획법, 배열, 조합론, 구현
정답자
아직 제출이 없습니다

문제

상근이가 사는 도시에는 남북 방향 도로가 ww개, 동서 방향 도로가 hh개 있다.

남북 방향 도로에는 서쪽부터 차례대로 1,2,…,w1, 2, \dots, w번이 매겨져 있고, 동서 방향 도로에는 남쪽부터 차례대로 1,2,…,h1, 2, \dots, h번이 매겨져 있다. 서쪽에서 ii번째 남북 방향 도로와 남쪽에서 jj번째 동서 방향 도로가 만나는 교차로를 (i,j)(i, j)라고 하자.

상근이는 교차로 (1,1)(1, 1)에 살고, 교차로 (w,h)(w, h)에 있는 회사까지 차로 출근한다. 차는 도로 위로만 움직일 수 있다. 회사에 최대한 빨리 도착하려고 상근이는 동쪽 또는 북쪽으로만 이동한다.

이 도시는 교통사고를 줄이기 위해, 교차로에서 방향을 바꾼 차가 바로 다음 교차로에서 다시 방향을 바꿀 수 없도록 정해 두었다. 즉, 한 번 방향을 바꾼 뒤에는 한 블록만 이동하고 곧바로 또 방향을 바꿀 수 없으며, 적어도 두 블록을 직진한 뒤에야 다시 방향을 바꿀 수 있다.

ww와 hh가 주어졌을 때, 상근이가 출근할 수 있는 서로 다른 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 ww와 hh가 주어진다. (2≤w,h≤1002 \le w, h \le 100)

출력

첫째 줄에 상근이가 출근할 수 있는 경로의 개수를 100000100000으로 나눈 나머지를 출력한다.

힌트

교차로에서 방향을 바꾼 뒤에는 반드시 두 블록 이상 직진해야 다시 방향을 바꿀 수 있다. 다시 말해, 연이은 두 교차로에서 모두 방향을 바꿀 수는 없다. 예를 들어 w=3w = 3, h=4h = 4인 경우 조건을 만족하는 경로는 모두 55가지이다.

예제2

  1. 예제 1

    입력
    3 4
    
    예상 출력
    5
    
  2. 예제 2

    입력
    15 15
    
    예상 출력
    43688