롱케이크 1

문제

비버중학교의 오늘 급식 메뉴는 롱케이크이다. 케이크는 1번부터 n번까지 n조각이 한 줄로 붙어 있고, 학생 n명이 한 줄로 서서 차례대로 원하는 조각 하나를 골라 가져간다.

가져가려는 조각이 다른 조각과 붙어 있으면 빵칼로 잘라내야 한다.

• 양옆이 모두 남아 있으면 2번 자른다.
• 한쪽만 남아 있으면 1번 자른다. (반대쪽은 케이크의 끝이거나 이미 가져간 자리)
• 양쪽 다 케이크의 끝이거나 이미 가져간 자리면 자르지 않는다.

학생들이 고른 조각 번호가 차례대로 주어질 때, 빵칼을 1번 사용하는 학생의 수와 2번 사용하는 학생의 수를 구해 보자.