백준 3135 - 라디오 (백준 - 그리디)

https://www.acmicpc.net/problem/3135

3135번: 라디오

 

* 문제 요약

라디오에는 다음과 같은 버튼이 있다.

- 첫번째 버튼은 주파수를 1MHz 증가시킨다.

- 두번째 버튼은 주파수를 1MHz 감소시킨다.

- 나머지 N개의 버튼은 즐겨찾기 기능으로, 미리 지정된 주파수로 이동한다.

 

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

주파수 A에서 B로 갈 때 눌러야 하는 버튼 수의 최솟값을 구하자.

 

* 입력

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

둘째 줄엔 정수 N이 주어진다. (1 <= N <= 5)

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

 

* 출력

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

 

* 예시

 

* 해결 과정

- 변수 result 에 기본적으로 즐겨찾기 없이 A에서 B로 직접 이동하는데 필요한 버튼 클릭 횟수를 저장해둔다.

- 이후 반복문으로 입력받은 즐겨찾기 배열을 순서대로 탐색한다.

    * 기존의 result 값과, 각 즐겨찾기로 설정해둔 주파수에서 B로 이동하는데 필요한 버튼 클릭수 + 즐겨찾기 버튼 클릭 횟수 1 을 한 값을 비교해서 더 작은 값을 result 에 저장한다.

    * 위의 과정을 반복하여 A에서 B로 가는데 필요한 버튼 클릭 횟수 최솟값을 구한다.

- 양수, 음수값이 중요한게 아니라 주파수의 차이에 따른 버튼 클릭 횟수를 구하는것이 중요하기 때문에 Math.abs() 와 같이 절대값을 구하는 메서드를 적극적으로 활용한다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");

        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt(input[1]);

        int size = Integer.parseInt(br.readLine());
        int[] favorite = new int[size];

        for (int i = 0; i < favorite.length; i++) {
            favorite[i] = Integer.parseInt(br.readLine());
        }

        int result = Math.abs(a - b);

        for (int i = 0; i < favorite.length; i++) {
            result = Math.min(result, Math.abs((favorite[i] - b)) + 1);
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

반복문의 각 단계마다 조건에 따라서 최적의 값을 result 에 저장시켜가며 최솟값을 찾으면서, 각 반복에서의 결정이 이후 단계에 영향을 미치지 않으므로 그리디 알고리즘 문제라고 볼 수 있다.