백준 03135번 / 3135번 문제 링크
문제 이름 : 라디오
주 언어 : Python
태그 : 수학 / 그리디 알고리즘
solved.ac 등급 : Silven V (2023/05/29 확인)
문제 보기
문제 :
준하는 라디오 수집광으로 신제품의 라디오가 나올때마다 흥분을 금치 못한다고 한다.
최근 준하가 구입한 라디오는 매우 하이테크 한데, 그 라디오에는 다음과 같은 버튼이 있다.
- 첫 번째 버튼은 주파수를 1MHz 증가시킨다.
- 두 번째 버튼은 주파수를 1MHz 감소시킨다.
- 나머지 N개의 버튼은 즐겨찾기 기능으로, 미리 지정된 주파수로 이동한다.
준하는 몸이 안좋아 하루에 손가락을 몇 번 움직이지 못하기 때문에 우리의 도움이 필요하다.
현재 주파수 A와 듣고싶은 주파수 B가 주어질 때,
주파수 A에서 B로 갈 때 눌러야 하는 가장 적은 버튼수를 구해주자.
입력 :
첫 줄엔 정수 A와 B가 주어진다 (1 ≤ A, B < 1000, A ≠ B).
다음 줄엔 정수 N이 주어진다 (1 ≤ N ≤ 5).
다음 N개의 줄엔 미리 지정되어 있는 주파수가 주어진다 (주파수는 1000 보다 작다).
출력 :
주파수 A에서 B로 갈 때 눌러야 하는 버튼수의 최솟값을 출력한다.
1번, 2번 버튼만 있다고 치면 주파수 X에서 주파수 Y로 가려면, 최소 $|X - Y|$번의 주파수 조작이 있어야 합니다. ($|x|$는 절댓값 함수 )
따라서 다음과 같은 경우의 수가 있습니다.
1. 1번 버튼이나 2번 버튼만을 이용해 주파수 A에서 B로 간다 -> 답은 $|A - B|$
2. 주파수 A에서 미리 즐겨찾기 되어있는 주파수 C로 가서 B로 간다 -> 답은 $1 + |C - B|$ (즐겨찾기 버튼을 누르는 그 1번까지 계산)
따라서 두 가지 경우의 수 중에서 가장 짧은 것을 출력해주면 됩니다.
-번째 푼 문제 (2022/--/--)