[백준] S4 3135번 라디오 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

3135번: 라디오

[문제] 

준하는 라디오 수집광으로 신제품의 라디오가 나올때마다 흥분을 금치 못한다고 한다.

최근 준하가 구입한 라디오는 매우 하이테크 한데, 그 라디오에는 다음과 같은 버튼이 있다.

• 첫 번째 버튼은 주파수를 1MHz 증가시킨다.
• 두 번째 버튼은 주파수를 1MHz 감소시킨다.
• 나머지 N개의 버튼은 즐겨찾기 기능으로, 미리 지정된 주파수로 이동한다.

준하는 몸이 안좋아 하루에 손가락을 몇 번 움직이지 못하기 때문에 우리의 도움이 필요하다.

현재 주파수 A와 듣고싶은 주파수 B가 주어질 때, 

주파수 A에서 B로 갈 때 눌러야 하는 가장 적은 버튼수를 구해주자.

[입력]

첫 줄엔 정수 A와 B가 주어진다 (1 ≤ A, B < 1000, A ≠ B).

다음 줄엔 정수 N이 주어진다 (1 ≤ N ≤ 5).

다음 N개의 줄엔 미리 지정되어 있는 주파수가 주어진다 (주파수는 1000 보다 작다).

[출력]

주파수 A에서 B로 갈 때 눌러야 하는 버튼수의 최솟값을 출력한다.

 

 

---

[풀이]

1. 현재 주파수와 듣고싶은 주파수의 차이를 min에 저장해둔다.

2. 즐겨찾기로 저장된 주파수를 입력받아 듣고 싶은 주파수와 즐겨찾기 주파수의 차이와 min을 비교해 최솟값을 갱신해준다.

3. 2를 반복하고 끝나면 최소값을 출력한다.

[접근]

1. 그리디 문제로 어떻게 풀면 될 지 생각해보았다.

2. 듣고싶은 주파수와 각 즐겨찾기와 현재 주파수의 차이를 구해 최솟값을 구하면 된다고 생각했다.

[코드]

package BOJ_silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_S4_3135 {
	static int a; // 현재
	static int b; // 듣고싶은
	static int n; // 즐겨찾기 개수
	static int min; // 최소값 계산용

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 입력받기
		a = Integer.parseInt(st.nextToken());
		b = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(br.readLine());
		
		min = Math.abs(a - b); // 현재 주파수와 듣고싶은 주파수의 차이
		
		// 즐겨찾기 입력받기
		for (int i = 0; i < n; i++) {
			// 즐겨찾기 값을 받아서 저장
			int favorite = Integer.parseInt(br.readLine());
			
			// (즐겨찾기와 듣고싶은 주파수의 차이) + 즐겨찾기로 이동하는 수 +1 vs 지금까지 최소 차이 
			min = Math.min(Math.abs(b - favorite) + 1, min);
		}
		
		// 최소 차이 출력
		System.out.println(min);
	}
}