경우의 수의 합

면접 대비

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

요약
양의 정수 n, m이 주어질 때 0 <= x <= n, 0 <= y <= m인 모든 정수 순서쌍 (x, y)의 개수를 구한다.
난이도

쉬움10점 중 3점

유형
수학, 조합론, 완전 탐색
정답자
아직 제출이 없습니다

문제

00 이상의 정수 a,b,ca, b, c에 대해, 0≤x≤a0 \le x \le a, 0≤y≤b0 \le y \le b, x+y=cx + y = c를 모두 만족하는 정수 순서쌍 (x,y)(x, y)의 개수를 f(a,b,c)f(a, b, c)라고 합시다.

예를 들어 0≤x≤20 \le x \le 2, 0≤y≤30 \le y \le 3, x+y=3x + y = 3을 만족하는 정수 순서쌍 (x,y)(x, y)는 (0,3),(1,2),(2,1)(0, 3), (1, 2), (2, 1)의 33개이므로, f(2,3,3)=3f(2, 3, 3) = 3입니다.

양의 정수 n,mn, m이 주어질 때

∑_i=0n+mf(n,m,i)=f(n,m,0)+f(n,m,1)+⋯+f(n,m,n+m)\sum\_{i=0}^{n+m} f(n, m, i) = f(n, m, 0) + f(n, m, 1) + \cdots + f(n, m, n+m)

을 구하세요.

예를 들어 n=2,m=1n = 2, m = 1인 경우, f(2,1,0)=1,f(2,1,1)=2,f(2,1,2)=2,f(2,1,3)=1f(2, 1, 0) = 1, f(2, 1, 1) = 2, f(2, 1, 2) = 2, f(2, 1, 3) = 1입니다. 따라서 구하려는 답은 1+2+2+1=61 + 2 + 2 + 1 = 6입니다.

입력

첫 번째 줄에 양의 정수 n,mn, m이 띄어쓰기로 구분되어 주어집니다. (1≤n,m≤1001 \le n, m \le 100)

출력

첫 번째 줄에 문제의 정답을 출력합니다.

예제3

  1. 예제 1

    입력
    1 1
    
    예상 출력
    4
    
  2. 예제 2

    입력
    2 1
    
    예상 출력
    6
    
  3. 예제 3

    입력
    2 3
    
    예상 출력
    12