[백준] 라디오 : 3135번 - Python

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

3135번: 라디오

 

 

 

문제를 풀면서 몰랐던 개념

 

- 특정 값이 주어졌을 때, 리스트에서 가장 가까운 값을 찾아내는 방법

: 두 수의 차(거리)를 구해서 가장 작은 것 부터 나열하면 된다! (절댓값을 사용할 것)

리스트와 딕셔너리 모두 사용가능!!!

 

 

 

문제의 접근 방법

 

이 문제는 두 가지 케이스로 나눌 수 있다.

(1) 첫 번째 혹은 두 번째 버튼을 눌러서 +-1씩 주파수를 증가/감소 시키는 방법

(2) 즐겨찾기 버튼을 누른 후 (1)의 과정을 수행하는 방법

-> 이 때, 최소한으로 버튼을 누르기 위해서는 즐겨찾기 주파수와 목표 주파수 B의 차이가 가장 작게 만들어 주어야 함.

 

(1),(2)의 값을 비교하여 더 작은 값을 구하면 주파수 A에서 B로 갈 때 눌러야 하는 최소 횟수를 알 수 있다.

 

 

 

내가 막혔던 부분

 

- 즐겨찾기에 저장되어있는 주파수들의 조합으로 B의 주파수에 도달해야 한다고 생각함.

- 증가/감소는 어차피 한 번 할 때마다 횟수에 들어가기 때문에 +-와는 상관 없다는 것을 늦게 깨달음.

 

 

 

문제 풀이 방법

 

(1) 주파수 A, B의 값을 입력 받기

 

(2) 정수 N의 값을 입력받아 N개의 줄에 미리 지정되어 있는(즐겨찾기) 주파수를 입력받기 + 리스트 arr에 저장하기

 

(3) 주파수가 1000보다 작다고 했으므로, 각 주파수 간의 차이가 1000을 넘지는 않으니까 최소 차(위에서 설명한 2번 방법 참고)를 저장할 변수 min_value의 초기 값을 1001로 설정해두기

 

(4) 나중에 즐겨찾기 주파수와 목표 주파수 B의 차이가 최소가 되도록 만드는 즐겨찾기 주파수를 저장하기 위한 변수 idx를 0으로 초기화 하여 선언하기

 

(5) 즐겨찾기 주파수들이 저장돼있는 리스트 arr에 반복문을 돌려서 임시 변수 temp에  "arr의 i번째 값(즐찾 주파수) - 목표 주파수 B" 의 절댓값 을 저장하기

 

(6) 만약 위에서 저장한 temp의 값이 최소 차 min_value의 값보다 작다면, temp가 최소 차를 의미한다는 뜻이므로 min_value의 값을 temp값으로 덮어씌워준다(바꿔준다).

 만약 더 temp의 값이 더 크다면 min_value의 값이 여전히 최소 차를 의미한다는 뜻이므로 그대로 두고 다시 반복문 실행한다.(continue)

 

(7) (6)의 과정에서 min_value값이 바뀌었다는 것은 그 값(즐겨찾기 주파수 - B의 주파수)이 최소라는 의미이므로 해당 즐겨찾기 주파수 값을 idx에 저장해준다.

 

(8) (5)~(7)의 과정을 반복하면 목표 주파수 B와 가장 가까운 즐겨찾기 주파수 값이 idx에 저장되어 있을 것이고 이는 이미 버튼을 한 번 눌렀다는 뜻이다.

 따라서, idx-B의 값 더하기 1(이미 즐겨찾기 주파수에 도달하기 위해 버튼을 한 번 눌렀기 때문에 +1을 해주고, 나머지 남은 차이는 버튼을 한 번씩 누름으로써 최종 주파수에 도달할 수 있음)을 해주면 문제의 접근 방법에서 언급했던 2번 케이스의 결과 값이 나오는 것이다.

 만약, 문제의 접근 방법에서 언급했던 (1)번 케이스로 진행해야 하는 경우에는 그냥 주파수 A - 주파수 B 의 절댓값이 버튼을 최소로 누를 수 있는 방법이기 때문에 -> 두 가지 값을 비교하여 최솟 값을 출력하면 됨!!!

 

 

 

소스코드

A, B = map(int, input().split())
N = int(input())

arr = []
[arr.append(int(input())) for _ in range(N)]

min_value = 1001
idx = 0
for i in arr:
    temp = abs(i - B)
    if min_value > temp:
        min_value = temp
        idx = i

print(min(abs(A-B), (abs(idx-B)+1)))