문제 바로가기
문제:
생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤 케이크를 준비했다. 롤 케이크에는 장식이 존재해서 특정 위치에서만 자를 수 있다. 주성이는 롤 케이크 조각을 파티에 올 친구의 수 만큼 준비하고 싶어서, 가장 작은 조각의 크기를 미리 알아보기로 했다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 그래서 몇 개의 수를 목록에 적어, 각 수만큼 조각을 만들었을 때 가장 작은 조각의 길이의 최댓값을 구하려고 한다. 예를 들어 70cm의 롤 케이크에 자를 수 있는 지점이 5군데(10cm, 20cm, 35cm, 55cm, 60cm)가 있다고 하자. 만약 목록에 적힌 수 중 하나가 3이라면 이때 가장 작은 조각의 길이는 최대 15cm이다. 예를 들어 20cm, 35cm, 55cm 지점을 자를 때 최대가 된다.
입력:
첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 지점을 나타내는 정수 Si가 주어진다. (1 ≤ Si < L) 다음 N줄에 걸쳐 자르는
횟수를 나타내는 정수 Qi가 주어진다. (1 ≤ Qi ≤ M) Si는 오름차순으로 주어지고 중복되는 수는 없으며, Qi도 마찬가지이다.
출력:
N개 줄에 걸쳐 각 목록에 있는 횟수대로 롤 케이크를 잘랐을 때 가장 작은 조각의 길이의 최댓값을 출력한다.
풀이:
시도1.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m, l = map(int,input().split())
S = [0] + [int(input()) for i in range(m)] + [l]
Q = [int(input()) for i in range(n)]
be_S = sorted([S[i]-S[i-1] for i in range(1,len(S))])
for i in range(n):
print(be_S[-Q[i]+1])
아이디어 : 이분 탐색 안쓰고 일단 케이크 자르는 크기를 새로운 be_s 에 저장
10, 20, 35, 55, 60 일때 0 부터 l 까지니깐
[0, 10, 20, 35, 55, 60, 70]
각 차이를 저장 하고 정렬
[10,10,15,20,5,10]
[5, 10, 10, 10, 15, 20]
1번 자르면 2개가나오고 2개 자르면 3개가 나오니깐 1개를 덜 잘라야해서 .be_S[-Q[i] +1] 을 해줬지만 5 프로 에서틀렸다
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m, l = map(int,input().split())
S = [int(input()) for i in range(m)] +[l]
Q = [int(input()) for i in range(n)]
def find_count(mid):
# 잘라서 나오는 갯수, 자르고 나서 위치 저장한 변수
cnt,temp = 0, 0
for i in S:
# 자른 크기가 잘라야 하는 값보다 크면
if i - temp >= mid:
# 자를 수 있으므로 갯수 추가
cnt += 1
# 그 다음 자를 위치를 위해 이동
temp = i
return cnt
for i in Q:
# 제일 작은크기는1, 제일 큰 크기는 l
left = 1; right = l; res = 0
while left <= right:
# 잘라야 하는 값
mid = (left + right) // 2
# mid 를 들고 갔을때 몇개의 조각이 나오는지 확인
count = find_count(mid)
#조각이 많이 나오면 잘라야 하는 크기를 늘리고
if count > i:
left = mid +1
res = max(mid,res)
# 조각이 적게 나오면 잘라야 하는 크기를 줄인다.
else:
right = mid-1
print(res)
이분탐색으로 풀어줘야 한다...
댓글