만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

벽 속의 또 다른 벽돌

시간 제한2초메모리 제한2048 MB

요약
1x2 벽돌과 1x3 벽돌로 길이 l, 높이 h인 벽을 쌓되 이음새가 위아래로 겹치지 않게 하면서, 필요한 1x3 벽돌의 최소 개수를 구합니다.
난이도

보통10점 중 7점

유형
동적 계획법, 비트 연산
정답자
아직 제출이 없습니다

문제

앨리스는 장난감 벽을 쌓는 것을 좋아한다. 그녀에게는 1×21 \times 2 벽돌이 많이 있고, 1×31 \times 3 벽돌은 개수가 제한되어 있다. 두 종류의 벽돌 모두 높이가 1이며, 회전할 수 없다.

앨리스는 이 벽돌로 두께가 1이고 길이가 ll, 높이가 hh인 벽을 쌓는다. 어떤 이음새도 바로 위에 다른 이음새가 없으면 그 벽을 단단한 벽이라고 한다.

좋은 이음새 배치나쁜 이음새 배치단단한 7×47 \times 4 벽

길이가 ll, 높이가 hh인 단단한 벽을 쌓는 데 필요한 1×31 \times 3 벽돌의 최소 개수를 구하라.

입력

첫 줄에 벽의 길이 ll과 높이 hh를 나타내는 두 정수가 주어진다 (5≤l≤10005 \le l \le 1000; 2≤h≤10002 \le h \le 1000).

출력

길이가 ll, 높이가 hh인 단단한 벽을 쌓는 데 필요한 1×31 \times 3 벽돌의 최소 개수를 출력한다.

길이가 ll, 높이가 hh인 단단한 벽은 항상 쌓을 수 있다.

예제1

  1. 예제 1

    입력
    7 4
    
    예상 출력
    4