20200305 알고리즘
1. 마구간 정하기
N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, …, xN의 좌표를 가지며, 마 구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요.
▣ 입력설명 첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 한 줄에 하나씩 주어집니다.
▣ 출력설명 첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.
▣ 입력예제 1
5 3
1
2
8
4
9▣ 출력예제 1
3
Solution
# 두 말 의 거리 최대값
import sys
sys.stdin = open("input25.txt", "rt")
n, m = map(int, input().split())
a = list()
for _ in range(n):
a.append(int(input()))
a.sort()
start = 1
end = a[n-1] - a[0]
res = -2147000000
def check(len):
cnt = 1
before = a[0]
for i in range(1, n):
if a[i] - before >= len:
cnt += 1
before = a[i]
return cnt
while start <= end:
mid = (start + end) // 2
if check(mid) >= m:
res = mid
start = mid + 1
else:
end = mid - 1
print(res)2. 회의실 배정
한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
▣ 입력설명 첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정 보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.
▣ 출력설명 첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
▣ 입력예제 1
5
1 4
2 3
3 5
4 6
5 7▣ 출력예제 1
3
Solution
import sys
sys.stdin = open("input26.txt", "rt")
n = int(input())
meeting = list()
for _ in range(n):
s, e = map(int, input().split())
meeting.append((s, e))
meeting.sort(key=lambda x: (x[1], x[0]))
res = 0
et = 0
for s, e in meeting:
if s >= et:
et = e
res += 1
print(res)3. 씨름 선수
현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습 니다. 현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다. 현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다. “다른 모든 지원자와 비교하여 키와 몸무게 중 적어도 하나는 다른 지원자보다 키가 크거나 몸무게가 많이 나가는 지원자만 뽑기로 했습니다.”
A 지원자가 다른 모든 지원자와 비교하여 키와 몸무게가 모두 작거나 가벼운 경우가 한 번이 라도 있다면 A지원자를 뽑지 않는다는 것입니다.
▣ 입력설명 첫째 줄에 지원자의 수 N(5<=N<=50)이 주어집니다. 두 번째 줄부터 N명의 키와 몸무게 정보가 차례로 주어집니다. 각 선수의 키와 몸무게는 모두 다릅니다.
▣ 출력설명 첫째 줄에 씨름 선수로 뽑히는 최대 인원을 출력하세요.
▣ 입력예제 1
5
172 67
183 65
180 70
170 72
181 60▣ 출력예제 1
3
Solution1
import sys
sys.stdin = open("input27.txt", "rt")
n = int(input())
people = list()
for _ in range(n):
h, w = map(int, input().split())
people.append((h, w))
people.sort(reverse=True)
largest=0
cnt=0
for x, y in people:
if y > largest:
largest = y
cnt += 1
print(cnt)
Solution2 (시간효율 bad)
import sys
sys.stdin = open("input27.txt", "rt")
n = int(input())
people = list()
for _ in range(n):
h, w = map(int, input().split())
people.append((h, w))
people.sort()
cnt = 0
for i in range(n-1):
w = people[i][1]
for j in range(i+1, n):
if w <= people[j][1]:
break
else:
cnt += 1
print(cnt+1) # + 첫번째 값4. 창고 정리
창고에 상자가 가로방향으로 일렬로 쌓여 있습니다. 만약 가로의 길이가 7이라면
열은 높이가 6으로 6개의 상자가 쌓여 있고, 2열은 3개의 상자, 3열은 9개의 상자가 쌓여 있 으며 높이는 9라고 읽는다. 창고 높이 조정은 가장 높은 곳에 상자를 가장 낮은 곳으로 이동하는 것을 말한다. 가장 높은 곳이나 가장 낮은 곳이 여러곳이면 그 중 아무거나 선택하면 된다.
창고의 가로 길이와 각 열의 상자 높이가 주어집니다. m회의 높이 조정을 한 후 가장 높은 곳 과 가장 낮은 곳의 차이를 출력하는 프로그램을 작성하세요.
▣ 입력설명 첫 번째 줄에 창고 가로의 길이인 자연수 L(1<=L<=100)이 주어집니다. 두 번째 줄에 L개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 100을 넘지 않습니다 세 번째 줄에 높이 조정 횟수인 M(1<=M<=1,000)이 주어집니다.
▣ 출력설명 M회의 높이 조정을 마친 후 가장 높은곳과 가장 낮은 곳의 차이를 출력하세요.
▣ 입력예제 1
10
69 42 68 76 40 87 14 65 76 81
50▣ 출력예제 1
20
Solution
import sys
sys.stdin = open("input28.txt", "rt")
n = int(input())
box = list(map(int, input().split()))
m = int(input())
maxIndex = n-1
minIndex = 0
for _ in range(m):
box[maxIndex] -= 1
box[minIndex] += 1
for i in range(n):
if box[i] < box[minIndex]:
minIndex = i
elif box[i] > box[maxIndex]:
maxIndex = i
print(box[maxIndex] - box[minIndex])Solution2
import sys
sys.stdin = open("input28.txt", "rt")
n = int(input())
box = list(map(int, input().split()))
m = int(input())
box.sort()
for _ in range(m):
box[0] += 1
box[n-1] -= 1
box.sort()
print(box[n-1] - box[0])- 매 루프마다 sort
5. 침몰하는 타이타닉
유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있 으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다. N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요.
▣ 입력설명 첫째 줄에 자연수 N(5<=N<=1000)과 M(70<=M<=250)이 주어집니다. 두 번째 줄에 N개로 구성된 몸무게 수열이 주어집니다. 몸무게는 50이상 150이하입니다. 각 승객의 몸무게는 M을 넘지는 않습니다. 즉 탈출을 못하는 경우는 없습니다.
▣ 출력설명 첫째 줄에 구명보트의 최소 개수를 출력합니다.
▣ 입력예제 1 5 140 90 50 70 100 60
▣ 출력예제 1
3
Solution
import sys
from collections import deque
sys.stdin = open("input29.txt", "rt")
n, maxWeight = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
weights = deque(a)
cnt = 0
while weights:
if len(weights) == 1:
cnt += 1
break
if weights[0] + weights[-1] <= maxWeight:
weights.popleft()
weights.pop()
cnt += 1
else:
weights.pop()
cnt += 1
print(cnt)pop(0)을 계속 하는 것은 비효율 > deque 자료구조 사용
![[HongDongUk]](/static/a60d793d17c3aad0361c9192a3b51381/a12fc/profile.png)