초콜릿 기둥의 비밀

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

요약

두께가 1cm인 흰색과 검은색 얇은 디스크, 두께가 k cm인 검은색 두꺼운 디스크를 색이 번갈아 가며 검은색으로 시작하고 끝나도록 쌓을 때, 총 두께가 l 이하인 서로 다른 배열의 수를 센다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

초콜릿 가게를 운영하는 웬디는 진열장에 초콜릿 원반을 쌓은 기둥을 놓으려고 한다. 쓸 수 있는 원반은 흰색 얇은 원반, 검은색 얇은 원반, 검은색 두꺼운 원반 세 가지다. 얇은 원반의 두께는 $1$ cm이고, 두꺼운 원반의 두께는 $k$ cm다. 원반은 유리 원통 안에 쌓는다.

기둥 하나는 다음 조건을 모두 만족해야 한다.

기둥은 원반을 적어도 하나 포함한다.
기둥에 쌓은 원반의 두께 합은 $l$ cm 이하다.
기둥의 맨 위 원반과 맨 아래 원반은 검은색이다.
흰색 원반 바로 위에 놓인 원반은 검은색이고, 검은색 원반 바로 위에 놓인 원반은 흰색이다.

그림 A.1에 기둥의 옆모습 여섯 개를 그렸다. $l = 5$ , $k = 3$ 일 때 웬디가 만들 수 있는 옆모습은 이 여섯 개가 전부다.

그림 A.1. $l = 5$ , $k = 3$ 일 때의 초콜릿 기둥 여섯 개

$l$ 과 $k$ 가 주어질 때, 웬디가 만들 수 있는 서로 다른 옆모습의 개수를 세어라.

입력

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

l k

$l$ 은 기둥에 쌓은 원반의 두께 합이 가질 수 있는 최댓값(cm)이고, $k$ 는 두꺼운 원반의 두께(cm)다. $l$ 과 $k$ 는 $1 \le l \le 100$ , $2 \le k \le 10$ 을 만족하는 정수다.

출력

가능한 서로 다른 옆모습의 개수를 출력한다.

예제5

예제 1
입력
```
5 3
```
예상 출력
```
6
```
예제 2
입력
```
9 10
```
예상 출력
```
5
```
예제 3
입력
```
10 10
```
예상 출력
```
6
```
예제 4
입력
```
20 5
```
예상 출력
```
86
```
예제 5
입력
```
100 2
```
예상 출력
```
3626169232670
```