[파이썬] 3011 이름 지어주기 (백준)

1. 문제 설명

문제 : 3011 - 이름 지어주기 https://www.acmicpc.net/problem/3011

사용 언어 : 파이썬 (Pypy3)

 

문제요약 :

구간 [A, B]에 들어있는 수 중에서 수열들의 각 수들 중 가장 차이가 큰 홀수를 구하여라.

---

2. 문제 풀이

해설 : 

우리는 기본적으로 2가지의 경우를 생각해 볼 수 있다.

 

첫 번째 경우는 기존의 수들 중에 답이 있는 것이다. 이 경우에는 아들들의 이름을 정렬시킨 후, i번째 수와 i+1번째 수의 중간으로 구할 수 있었다. 이는 (P[i]+P[i+1])/2로 구할 수 있다.

 

두 번째 경우는 A+1 혹은 B-1중 답이 있는 것이다. 이 경우에는 모든 아들들과의 거리 중 가장 짧은 거리를 비교하여 답을 구할 수 있었다. 아들이 최대 100명이기 때문에 O(N)으로 전체 탐색을 하거나 이분탐색 등의 방법으로 O(logN)으로 구할 수 있다.

 

코드 :

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

A += (1 if A%2 == 0 else 0)
B -= (1 if B%2 == 0 else 0)

cans = []

def change(x):
    if not A <= x <= B: return 0
    if x%2 == 1: return x

    if A <= x-1: return x-1
    elif x+1 <= B: return x+1

for i in range(N-1):
    temp = (names[i]+names[i+1])//2
    temp = change(temp)

    if temp: cans.append([temp, min(abs(temp-names[i]), abs(temp-names[i+1]))])

min_A, min_B = 2e9, 2e9
for i in range(N):
    min_A = min(min_A, abs(names[i]-A))
    min_B = min(min_B, abs(names[i]-B))
cans.append([A, min_A]); cans.append([B, min_B])

cans.sort(key=lambda x:-x[1])
print(cans[0][0])

---

코딩과 알고리즘 관련 글을 업로드하고 있습니다!

아직 배우는 중이라서 부족한 점이 있으면 댓글 남겨주시면 감사하겠습니다!!