자두나무
면접 대비시간 제한2초메모리 제한128 MB
T초 동안 나무 1과 2 중 떨어지는 자두 순서가 주어질 때, 나무 1에서 시작해 최대 W번 이동하며 잡을 수 있는 최대 자두 개수를 구합니다.
- 난이도
보통10점 중 5점
- 유형
- 동적 계획법
- 정답자
- 아직 제출이 없습니다
문제
자두는 자두 열매를 좋아해서 집에 두 그루의 자두나무를 심었다. 키가 작아 나무에서 직접 따지는 못하고, 열매가 떨어지는 순간에 그 나무 아래에 서 있어야 받아먹을 수 있다. 열매가 땅에 닿으면 먹을 수 없을 만큼 뭉개진다.
매초 두 나무 중 하나에서 열매가 하나 떨어진다. 자두는 한 나무 아래에서 다른 나무 아래로 1초보다 훨씬 짧은 시간에 이동할 수 있지만, 체력 때문에 많이 움직일 수 없다.
총 T초 동안 열매가 떨어지고, 자두는 최대 W번만 이동하려고 한다. 각 초에 어느 나무에서 열매가 떨어지는지가 주어질 때, 자두가 받을 수 있는 열매의 최대 개수를 구하라. 처음에는 1번 자두나무 아래에 서 있다. T는 1 이상 1,000 이하이고, W는 1 이상 30 이하이다.
입력
첫째 줄에 정수 T와 W가 주어진다. 다음 T개의 줄에는 각 초에 열매가 떨어지는 나무 번호가 1 또는 2로 주어진다.
출력
자두가 받을 수 있는 열매의 최대 개수를 한 줄에 출력한다.