스마트 TV 한 대를 구매하였다. 당연히 채널과 음량을 조정할 수 있는 리모콘도 함께 들어있었다. 그런데 리모콘의 버튼이 아래와 같이 총 8개만 존재하였다.
[채널-6], [채널-4], [채널–1], [채널+3], [채널+5], [채널+9]
[음량-1], [음량+1]
리모컨의 채널 조정은 존재하는 채널로만 이동 가능한데 TV채널은 1번부터 40번까지만 존재한다. 그래서 만약 1번 채널에서 [채널-6] 버튼을 누르면 무시될 것이다. 또한 38번 채널에서 [채널+9] 버튼을 누른다면 무시될 것이다.
위와 같은 조건에서 33번 채널에서 40번 채널로 이동하는 방법으로는,
① [채널+5], [채널-1], [채널+3]
② [채널+3], [채널-1], [채널+5]
③ [채널-1], [채널+5], [채널+3]
④ [채널-1], [채널+3], [채널+5]
⑤ [채널-1], [채널-1], [채널+9]
위 방법들 중 한 가지 방법으로 목표 채널로 이동할 수 있다.
(버튼 조작 중 채널 범위를 넘어서는 [채널+5], [채널+3], [채널-1] 등의 방법은 안됨)
이왕이면 빠르게 채널을 바꾸는 것이 좋을 것이다.
현재 채널과 목표 채널이 주어졌을 때, 최소 버튼 조작으로 목표 채널로 이동한다면 몇 번 만에 가능한지, 그리고 최소 버튼 조작의 방법이 몇 가지 존재하는지 알아내는 프로그램을 제작하시오.
위 예시에서는 33번 채널에서 40번 채널로 최소 3번의 버튼 조작으로 이동이 가능하며, 3번의 버튼 조작으로 이동하는 방법은 총 5가지 존재한다.