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

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

N-k-특수 집합의 개수

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

요약
1부터 n까지의 수 중 연속한 두 수를 함께 고르지 않으면서 합이 k보다 큰 부분집합의 개수를 센다.
난이도

보통10점 중 5점

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

문제

자연수들의 집합 XX가 다음 세 조건을 모두 만족하면 XX를 nn-kk-특수 집합이라고 한다.

  • XX의 모든 원소 xx는 1≤x≤n1 \le x \le n을 만족한다.
  • XX에 속한 모든 원소의 합이 kk보다 크다(엄밀히 크다).
  • XX는 연속한 두 자연수를 동시에 포함하지 않는다. 즉, 어떤 두 원소도 차가 정확히 11이 되지 않는다.

두 자연수 nn과 kk가 주어질 때, nn-kk-특수 집합의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 자연수 nn과 kk가 공백 하나로 구분되어 주어진다. (1≤n≤1001 \le n \le 100, 0≤k≤4000 \le k \le 400)

출력

첫째 줄에 주어진 nn과 kk에 대한 nn-kk-특수 집합의 개수를 나타내는 음이 아닌 정수 하나를 출력한다.

예제2

  1. 예제 1

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

    입력
    2 0
    
    예상 출력
    2