[BOJ]그리디
Coding Test Study 1
💻220928~221012 (브3~실4)
1. 대회 or 인턴 (브3) 2875
N, M, K = map(int, input().split())
while K > 0 :
if N/2 >= M :
N -= 1
K -= 1
else :
M -= 1
K -= 1
team = N//2 if N//2 < M else M
print(team)
2. 거스름돈(브2) 5585
money = int(input())
coin_array = [500, 100, 50, 10, 5] #배열에서 1은 없애줌
change = 1000-money
result = 0
for coin in coin_array :
result += change//coin
change %= coin
result += change #1원은 나눠도 똑같으므로 for문 밖에서 더 해줌
print(result)
3. 시험감독(브2) 13458
import sys
N = int(input())
A = list(map(int, sys.stdin.readline().split()))
B, C = map(int, input().split())
result = N
for a in A :
a -= B
if a > 0 : # a가 0보다 클 때만 result 계산
result += a//C
if a%C > 0 :
result += 1
print(result)
4. 캠핑(브1) 4796
case = []
while True :
result = 0
L, P, V = map(int, input().split())
if L==0 and P==0 and V== 0 :
break
result += (V//P)*L
result += L if V%P > L else V%P
case.append(result)
i = 1
for c in case :
print('Case %d: %d' %(i, c))
i += 1
5. DNA(실5) 1969
import sys
from collections import Counter
N, M = map(int, input().split())
s = [input() for _ in range(N)]
hd = 0
result = []
for i in range (M) :
dna = []
for j in range(N) :
dna.append(s[j][i])
dna.sort()
cnt = Counter(dna)
result.append(cnt.most_common(1)[0][0])
hd += N-cnt.most_common(1)[0][1]
print(''.join(s for s in result))
print(hd)
6. 카약과 강풍(실5) 2891
N, S, R = map(int, input().split())
arr = [0]*(N+1)
s_arr = list(map(int, input().split()))
r_arr = list(map(int, input().split()))
for s in s_arr :
arr[s-1] = -1
for r in r_arr :
arr[r-1] += 1 # 부서졌는데 카약을 하나 더 가져왔다면 0으로 된다
for i in range(N) :
if (arr[i] == 1) :
if(arr[i-1] == -1) :
arr[i-1] = 0
arr[i] = 0
continue
if(arr[i+1] == -1) :
arr[i+1] = 0
arr[i] = 0
continue
print(arr.count(-1))
7. 동전 0(실4) 11047
N, K = map(int, input().split())
A = [int(input()) for i in range(N)]
A.sort(reverse=True) #내림차순
cnt = 0
i = 0
while K > 0 :
cnt += K//A[i]
K %= A[i]
i += 1
print(cnt)
8. Project Teams(실4) 20044
n = int(input())
s = list(map(int, input().split()))
s.sort()
G = []
for i in range (n) :
G.append(s[i] + s[n*2 - i - 1])
print(min(G))
9. 30(실4) 10610
N = int(input())
n = list(map(int, str(N)))
n.sort(reverse=True)
if(n[-1] != 0) :
print(-1)
else :
if(sum(n)%3 == 0) :
print(''.join(map(str, n)))
else :
print(-1)
10. ATM(실4) 11399
N = int(input())
P = list(map(int, input().split()))
P.sort()
result = []
s = 0
for i in range (N) :
s += P[i]
result.append(s)
print(sum(result))
💻221013~221019 (실4~실2)
11. 문서검색(실4) 1543
sen = input()
word = input()
result = 0
i = 0
while i < len(sen) :
cnt = 0
if word[0] == sen[i] :
j = 0
for j in range (len(word)) :
if i+j < len(sen) and word[j] == sen[i+j] :
cnt += 1
if cnt == len(word) :
i += cnt
result += 1
else :
i += 1
print(result)
12. 걷기(실4) 1459
X, Y, W, S = map(int, input().split())
if (W*2 <= S) : #직선 시간 2배가 대각선 시간보다 작거나 같을 때
print((X+Y)*W) #전부다 직선으로 계산
elif (W <= S and S < W*2): #대각선 시간이 직선 시간과 직선 시간 2배 사이일 때
result = 0
result += (max(X, Y) - min(X, Y))*W
result += min(X, Y)*S
print(result) #최대한 대각선으로 가고 나머지는 직선으로 계산
else : #대각선 시간이 직선시간보다 작을 때
result = 0
result += min(X, Y)*S
if (max(X, Y) - min(X, Y))%2 == 0 :
result += (max(X, Y) - min(X, Y))*S
else :
result += ((max(X, Y) - min(X, Y))-1)*S + W
print(result) #직선 2개면 대각선으로 가기
13. 로프(실4) 2217
N = int(input())
W = [int(input()) for i in range(N)]
W.sort()
result = 0
for i in range (N) :
if(W[i]*(N-i) >= result) :
result = W[i]*(N-i)
print(result)
14. 병든나이트(실3) 1783
N, M = map(int, input().split())
if N == 1 :
result = 1
elif N == 2 :
result = min(4, (M+1)//2)
elif M < 7 :
result = min(4, M)
else :
result = M-2
print(result)
15. 모두의 마블(실3) 12845
n = int(input())
L = list(map(int, input().split()))
gold = 0
for i in range (n-1) :
max_value = max(L)
max_idx = L.index(max(L))
if max_idx == 0 :
gold += L[max_idx+1] + max_value
L.remove(L[max_idx+1])
elif max_idx == len(L)-1 :
gold += L[max_idx-1] + max_value
L.remove(L[max_idx-1])
else :
card = max(L[max_idx-1], L[max_idx+1])
gold += card + max_value
L.remove(card)
print(gold)
16. 등수 매기기(실3) 2012
import sys #sys로 안 하면 시간초과 나옴
N = int(input())
S = [int(sys.stdin.readline()) for i in range(N)]
S.sort()
result = 0
for i in range(N) :
result += abs(S[i]-(i+1))
print(result)
17. Yonsei ToTo(실3) 12018
#입력
import sys
n, m = map(int, sys.stdin.readline().split())
P = []
L = []
mileage = []
for i in range (n) :
p, l = map(int, sys.stdin.readline().split())
P.append(p)
L.append(l)
mile = list(map(int, sys.stdin.readline().split()))
mileage.append(mile)
#강의를 들을 수 있는 마일리지 최솟값을 result 리스트에 넣기
result = []
for i in range (n) :
mileage[i].sort(reverse=True)
if (P[i] >= L[i]) :
result.append(mileage[i][L[i]-1])
else :
result.append(1)
#result를 오름차순 정렬하여 마일리지를 다 쓸 때까지 카운트해줌
result.sort()
lecture = 0
for i in range(n) :
if result[i] <= m :
lecture += 1
m -= result[i]
print(lecture)
18. 주유소(실3) 13305
import sys
N = int(input())
R = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))
# 최솟값을 첫번째 도시로 초기화
m = C[0]
distance = 0
result = 0
# for문 돌때마다 거리 추가
# 최솟값이 갱신될 때 최솟값x거리를 더해주고 최솟값 갱신 후 거리도 0으로 초기화
for i in range(N-1) :
if C[i] < m :
result += m*distance
m = C[i]
distance = 0
distance += R[i]
# 남은 거리 계산해서 더해줌
result += m*distance
print(result)
19. 잃어버린 괄호(실2) 1541
M = input()
# '-' 기준으로 문자열 나누기
math = M.split('-')
# '+' 기준으로 또 나누기
# math2는 2차원 리스트가 됨
math2 = []
for i in math :
math2.append(list(map(int, i.split('+'))))
# math2 각 리스트의 합을 math3에 저장
math3 = []
for i in math2 :
math3.append(sum(i))
# 첫 번째 수에서 뒤에 수들을 다 빼준다
result = math3[0]
for i in range (1, len(math3)) :
result -= math3[i]
print(result)
20. 주식(실2)
import sys
input = sys.stdin.readline
T = int(input())
N = []
S = []
answer = []
for i in range (T) :
N = int(input())
S = list(map(int, input().split()))
m = S[N-1]
result = 0
for j in range (N-1, -1, -1) : # 뒤에서부터
if S[j] < m : # 현재값이 max값보다 작다면 차이를 더해줌
result += m-S[j]
else : # 크다면 max값 갱신
m = S[j]
answer.append(result)
for i in range(T) :
print(answer[i])
💻221020~221102 (실2~실1)
21. 체인(실2) 2785
import sys
N = int(input())
L = list(map(int, sys.stdin.readline().split()))
L.sort()
result = 0
while len(L) > 1 :
if L[0] == 1 : # 첫 번째 원소가 1이면 첫 번째 원소를 두개 붙이는데 사용하므로 삭제한다
del L[0]
L.pop()
result += 1
else : # 첫 번째 원소가 1이 아닐 때 첫 번째 체인 하나를 사용하여 두개를 붙임
L.pop()
L[0] -= 1
result += 1
print(result)
22. 초콜릿 식사(실2) 2885
K = int(input())
num = 1
cnt = 0
array = []
array.append(num)
while num < K :
num *= 2
array.append(num)
array.sort(reverse=True)
cnt = 0
i = 0
while K > 0:
if K >= array[i] :
K -= array[i]
i += 1
print(array[0], i-1)
23. 종이접기(실2) 1802
import sys
T = int(sys.stdin.readline())
for i in range (T) :
P = input()
P = list(map(int, str(P)))
# 2^N-1 길이만 입력이므로 N을 구할 수 있다
N = 0
length = len(P)+1
while length > 1 :
length /= 2
N += 1
# 플래그 1이고, 반으로 계속 접으면서 마주보는 값의 합이 1이 아니면 플래그를 0으로 해줌
f = 1
for j in range (N, 0, -1) :
n = 2**j-2
for k in range(n//2) :
if P[k]+P[n-k] != 1 :
f = 0
# 플래그가 여전히 1이라면 yes, 0으로 바뀌었다면 no
if f == 1 :
print('YES')
else :
print('NO')
24. 회의실배정(실1) 1931
import sys
input = sys.stdin.readline
N = int(input())
C = []
for i in range (N) :
C.append(list(map(int, input().split())))
C.sort(key = lambda x: (x[1] , x[0])) #1.끝난 시간 2.시작 시간 기준으로 정렬
end = C[0][1]
result = 1
for i in range (1, N) :
if C[i][0] >= end : #시작시간이 앞에 끝난 시간 보다 크거나 같으면
result += 1 #result 값 올려주고
end = C[i][1] # 끝난 시간 갱신
print(result)
25. 흙길 보수하기(실1) 1911
import sys
input = sys.stdin.readline
N, L = map(int, input().split())
pool = []
for i in range(N) :
pool.append(list(map(int, input().split())))
pool.sort()
result = 0
start = pool[0][0]
end = ((pool[0][1]-start+L-1)//L)*L + start #start값에서 L의 배수를 더한 값
for i in range (N) :
if end < pool[i][0] : #end값이 현재 웅덩이 시작값보다 작다면
result += (end-start+L-1)//L #널빤지 개수 더해줌
start = pool[i][0] #start값을 현재 웅덩이 시작값으로 갱신
end = ((pool[i][1]-start+L-1)//L)*L + start #end값을 start값에서 L의 배수 더한 값으로 갱신
else : #end값이 현재 웅덩이 시작값보다 크다면
end = ((pool[i][1]-start+L-1)//L)*L + start #end값만 갱신
result += (end-start+L-1)//L #마지막 널빤지 개수 더해줌
print(result)
26. 신입사원(실1) 1946
import sys
input = sys.stdin.readline
T = int(input())
R = ""
# 입력 받으면서 바로 해야함 안 그러면 3중 for문됨
for i in range (T) :
p = []
N = int(input())
for j in range (N) :
p.append(list(map(int, input().split())))
p.sort() # 서류 기준으로 정렬
result = 1 # 서류 1등은 무조건 선발됨
m = p[0][1] # 최솟값은 서류 1등의 면접 점수
for j in range(1, N) :
if m > p[j][1] : # 현재 사원이 앞 사람들 면접 1등보다 등수가 높으면 선발
m = p[j][1] # 최솟값 갱신
result += 1
R += (str(result) + '\n')
print(R)
💻221103~221109 (실5~골5)
27. 폴리오미노(실5) 1343
board = input()
board = board.replace('XXXX', 'AAAA')
board = board.replace('XX', 'BB')
if 'X' in board :
print(-1)
else :
print(board)
28. 알바생 강호(실4) 1758
import sys
input = sys.stdin.readline
N = int(input())
G = [int(input()) for _ in range(N)]
G.sort(reverse=True)
result = 0
for i in range(N) :
if G[i]-i > 0 :
result += G[i]-i
print(result)
29. 에너지 드링크(실3) 20115
import sys
input = sys.stdin.readline
N = int(input())
X = list(map(int, input().split()))
X.sort()
result = 0
for i in range(N-1) :
result += X[i]/2
result += X[N-1]
print(result)
30. 서강근육맨(실3) 20300
import sys
input = sys.stdin.readline
N = int(input())
M = list(map(int, input().split()))
M.sort()
result = []
#N이 홀수면 마지막 원소를 배열에 미리 넣어줌
if N % 2 == 1 :
result.append(M.pop(N-1))
#마주보는 값들의 합을 배열에 넣어줌
for i in range(len(M)//2) :
result.append(M[i]+M[len(M)-i-1])
print(max(result))
31. 블로그2(실2) 20365
N = int(input())
blog = input()
result = 1
if blog[0] == 'B' :
r_cnt = blog.split('B')
r_cnt = ' '.join(r_cnt).split()
result += len(r_cnt)
if blog[0] == 'R' :
b_cnt = blog.split('R')
b_cnt= ' '.join(b_cnt).split()
result += len(b_cnt)
print(result)
32. 행렬(실1) 1080
N, M = map(int, input().split())
A = []
B = []
for i in range(N):
A.append(list(map(int, input())))
for i in range(N):
B.append(list(map(int, input())))
if N < 3 or M < 3 :
if A == B :
print(0)
else :
print(-1)
else :
result = 0
for i in range(N-2):
for j in range (M-2):
if A[i][j] != B[i][j]:
A[i][j] = int(not A[i][j])
A[i][j+1] = int(not A[i][j+1])
A[i][j+2] = int(not A[i][j+2])
A[i+1][j] = int(not A[i+1][j])
A[i+1][j+1] = int(not A[i+1][j+1])
A[i+1][j+2] = int(not A[i+1][j+2])
A[i+2][j] = int(not A[i+2][j])
A[i+2][j+1] = int(not A[i+2][j+1])
A[i+2][j+2] = int(not A[i+2][j+2])
result += 1
if A == B :
print(result)
else :
print(-1)
33. 꿀 따기(골5) 21758
import sys
input = sys.stdin.readline
N = int(input())
X = list(map(int, input().split()))
# 벌-꿀통-벌
result1 = 0
part1 = 0
part2 = sum(X)-X[0]-X[N-1]
for i in range (1, N-1) :
part2 -= part1
part1 += X[i]
if part1+part2 > result1 :
result1 = part1+part2
# 벌-벌-꿀통
result2 = 0
part1 = sum(X)-X[0]
part2 = sum(X)-X[0]
for i in range (1, N) :
part2 -= X[i]
s = (part1-X[i])+part2
if s > result2 :
result2 = s
# 꿀통-벌-벌
X.reverse()
result3 = 0
part1 = sum(X)-X[0]
part2 = sum(X)-X[0]
for i in range (1, N) :
part2 -= X[i]
s = (part1-X[i])+part2
if s > result3 :
result3 = s
# 세개 다 구해서 그 중 제일 큰 값 출력
result = max(result1, result2, result3)
print(result)
💻221110~221116 (실5~골5)
34. 사과 담기 게임(실5) 2828
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
J = int(input())
X = [int(input()) for _ in range(J)]
start = 1
end = M
result = 0
for i in range (J):
if X[i] < start :
result += start-X[i]
end -= start-X[i]
start -= start-X[i]
if X[i] > end :
result += X[i]-end
start += X[i]-end
end += X[i]-end
print(result)
35. 2+1 세일 (실4) 11508
import sys
input = sys.stdin.readline
N = int(input())
C = [int(input()) for _ in range(N)]
C.sort(reverse=True)
result = 0
if len(C) < 2 :
result = sum(C)
else :
for i in range(N) :
if i % 3 != 2 :
result += C[i]
print(result)
36. 햄버거 분배(실3) 19941
N, K = map(int, input().split())
T = list(input())
result = 0
for i in range (N) :
if T[i] == 'P':
for j in range (i-K, i+K+1):
if j >= 0 and j < N and T[j] == 'H':
T[j] = '0'
T[i] = '0'
result += 1
break
print(result)
37. A -B(\실2) 16953
import sys
input = sys.stdin.readline
A, B = map(int, input().split())
result = 0
while True :
if B%10 == 1 :
B //= 10
result += 1
elif B%2 == 0 :
B //= 2
result += 1
else :
break
if B <= A :
break
if A == B :
print(result+1)
else :
print(-1)
38. 민겸 수(실2) 21314
import sys
input = sys.stdin.readline
num = input().rstrip()
big = ''
small = ''
m = 0
for i in range (len(num)) :
if num[i] == 'M' :
m += 1
else :
if m > 0 :
big += str(5*(10**m))
small += str(10**(m-1)) + '5'
else :
big += '5'
small += '5'
m = 0
if m > 0 :
big += '1' * m
small += str(10**(m-1))
print(big)
print(small)
39. 볼 모으기(실1) 17615
import sys
input = sys.stdin.readline
N = int(input())
ball = input().rstrip()
#빨간 공 뒤로
result1 = 0
cnt = 0
f = 0
for i in range (N):
if ball[i] == 'R':
if f == 1 :
result1 += cnt
cnt = 0
f = 0
cnt += 1
else :
f = 1
if f == 1 :
result1 += cnt
#빨간 공 앞으로
result2 = 0
cnt = 0
f = 0
for i in range (N-1, -1, -1):
if ball[i] == 'R':
if f == 1 :
result2 += cnt
cnt = 0
f = 0
cnt += 1
else :
f = 1
if f == 1 :
result2 += cnt
#파란 공 뒤로
result3 = 0
cnt = 0
f = 0
for i in range (N):
if ball[i] == 'B':
if f == 1 :
result3 += cnt
cnt = 0
f = 0
cnt += 1
else :
f = 1
if f == 1 :
result3 += cnt
#파란 공 앞으로
result4 = 0
cnt = 0
f = 0
for i in range (N-1, -1, -1):
if ball[i] == 'B':
if f == 1 :
result4 += cnt
cnt = 0
f = 0
cnt += 1
else :
f = 1
if f == 1 :
result4 += cnt
print(min(result1, result2, result3, result4))
40. 전구와 스위치(골5) 2138
N = int(input())
A = list(map(int, str(input())))
B = list(map(int, str(input())))
a1 = A[:]
a2 = A[:]
#첫 번째 스위치 누름
a1[0] = int(not a1[0])
a1[1] = int(not a1[1])
result1 = 1
for i in range (1, N):
if a1[i-1] != B[i-1]:
a1[i-1] = int(not a1[i-1])
a1[i] = int(not a1[i])
if i < N-1:
a1[i+1] = int(not a1[i+1])
result1 += 1
#첫 번째 스위치 안 누름
result2 = 0
for i in range (1, N):
if a2[i-1] != B[i-1]:
a2[i-1] = int(not a2[i-1])
a2[i] = int(not a2[i])
if i < N-1:
a2[i+1] = int(not a2[i+1])
result2 += 1
if a1 == B and a2 == B:
print(min(result1, result2))
elif a1 == B :
print(result1)
elif a2 == B :
print(result2)
else :
print(-1)
💻2023~2024(골5~골1)
27. 강의실 배정(골5) 11000
해결 방법
• 오름차순으로 정렬한다.(자동으로 S, T 작은 순으로 됨)
• 강의실 끝나는 시간을 heap으로 만든다. 가장 일찍 끝나는 강의실에 다음 시간표를 넣을 것이기 때문
• 가장 일찍 끝나는 강의실에도 넣을 수 없다면 그 시간표가 끝나는 시간을 heap에 넣는다.
예제 설명
h:[1] / [1, 3]의 1이 h[0]보다 크거나 같으므로 pop을 한 후 3을 넣는다.
h:[3] / [2, 4]의 2가 h[0]보다 작으므로 새로운 강의실을 만들어야 한다. 4를 넣는다.
h:[3, 4] / [3, 5]의 3이 h[0]보다 크거나 같으므로 강의실을 이어서 쓸 수 있다. 3을 pop한 후 5를 넣는다.
h:[4, 5] / 최종 h의 길이는 2이고 이것이 사용한 강의실 개수이다.
import sys
import heapq
input = sys.stdin.readline
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
arr.sort()
h = []
heapq.heappush(h, arr[0][0])
for i in range(N):
if arr[i][0] >= h[0]:
heapq.heappop(h)
heapq.heappush(h, arr[i][1])
print(len(h))
28. 최소 회의실 개수(골5) 19598
• 강의실 배정과 똑같이 풀면 된다.
import sys
import heapq
input = sys.stdin.readline
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
arr.sort()
h = []
heapq.heappush(h, arr[0][0])
for i in range(N):
if arr[i][0] >= h[0]:
heapq.heappop(h)
heapq.heappush(h, arr[i][1])
print(len(h))
29. 문자열복사(골5) 2195
• 끝까지 다 돌리면서 해당 문자열이 S 안에 있을 때마다 end값을 갱신해준다.
• 그럼 end값은 가장 긴 문자열의 마지막 인덱스가 될 것이고 이걸 current에 넣어준다.
• current와 P의 길이가 같아지면 break
import sys
input = sys.stdin.readline
S = input().rstrip()
P = input().rstrip()
current = 0
answer = 0
while True:
for i in range(current, len(P)):
if P[current:i+1] in S:
end = i+1
current = end
answer += 1
if current == len(P):
print(answer)
break
30. 뒤집기 3(골5) 1464
첫 번째 if문
• S의 부분 문자열이 정렬되지 않은 상태
• 오름차순 끝나는 지점이면서 첫 번째 값보다 작거나 같을 때
• 첫 번째 값과 비교하는 이유는 무조건 첫 번째 값이 제일 작아야하기 때문
BCDAF → DCBAF
두 번째 if문
• 첫 번째 정렬 후에 본인이 다음 값보다 크거나 같으면 사전순으로 다시 바꿔준다.
DCBAF → ABCDF
import sys
input = sys.stdin.readline
S = input().rstrip()
N = len(S)
for i in range(N-1):
if S[i] > S[i+1] and S[i+1] <= S[0]: #첫번째 값이 무조건 제일 작아야함
S = S[:i+1][::-1] + S[i+1:]
if S[i] >= S[i+1]: #사전순으로 다시 바꿔주기
S = S[:i+2][::-1] + S[i+2:]
print(S)
32. 회문(골5) 17609
• isPal은 현재 문자열이 팰린드롬인지 확인하는 함수
• 팰린드롬이 아니면 (start+1, end)와 (start, end-1)가 팰린드롬인지 확인한다.
import sys
input = sys.stdin.readline
T = int(input())
def isPal(string, start, end):
sliced = string[start:end+1]
return sliced == sliced[::-1]
for _ in range(T):
string = list(input().rstrip())
answer = 0
start = 0
end = len(string)-1
if isPal(string, start, end):
print(answer)
continue
while start < end:
if string[start] == string[end]:
start += 1
end -= 1
else:
if isPal(string, start+1, end) or isPal(string, start, end-1):
answer = 1
else:
answer = 2
break
print(answer)
33. 콘센트(골5) 23843
• 최소 힙을 쓰는 이유: 가장 빠른 시간(h[0])에 다음 기기를 충전해야하기 때문
• 내림차순 정렬을 해서 충전 긴 기기부터 충전해야 스택이 잘 들어간다.
오름차순 정렬했을 때 잘못된 결과
[0, 1]
[1, 1]
[1, 5]
[5, 5]
[5, 13]
내림차순 정렬했을 때 올바른 결과
[0, 8]
[4, 8]
[8, 8]
[8, 9]
[9, 9]
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
h = [0 for _ in range(M)]
for i in range(N):
root = heapq.heappop(h)
heapq.heappush(h, root+arr[i])
print(max(h))
34. 센서(골5) 2212
문제 해석
한 집중국이 거리 몇까지 수신할 수 있는지 계산하고
그 거리의 합을 구하면 된다.
예제 입력 1로 추가 설명
[1, 3, 6, 6, 7, 9]
-*-*--**-* → 같은 위치(6)면 생략해도 된다.
-(*-*)--(**-*) → 집중국1이 거리 2(1~3)를 수신, 집중국2가 거리 3(6~9)을 수신해서 답이 5이다.
해결 방법
센서 덩어리를 효율적으로 나누면 된다.
효율적이란? 두 센서의 거리가 '먼' 것부터 덩어리로 나누는 것
덩어리와 덩어리 사이는 집중국이 수신하지 않아도 되기 때문에 첫 번째 센서와 마지막 센서 거리에서 수신하지 않아도 되는 거리를 뺀다.
K개 덩어리로 나누어야 하므로 내림차순 후 앞에서 부터 K-1개까지만 전체 거리에서 빼야한다.
import sys
input = sys.stdin.readline
N = int(input())
K = int(input())
arr = list(map(int, input().split()))
# arr: [20, 3, 14, 6, 7, 8, 18, 10, 12, 15]
arr.sort()
# arr: [3, 6, 7, 8, 10, 12, 14, 15, 18, 20]
# 각 센서가 떨어져 있는 것으로 덩어리 나누기
diff = []
for i in range(1, N):
diff.append(arr[i]-arr[i-1])
# diff: [3, 1, 1, 2, 2, 2, 1, 3, 2]
diff.sort(reverse=True)
# diff: [3, 3, 2, 2, 2, 2, 1, 1, 1]
print(arr[N-1]-arr[0]-sum(diff[:K-1]))
35. 지뢰찾기(골4) 9082
• "*"가 이미 있는 부분을 먼저 계산하여 숫자를 뺀다.
• 그 후 현재 본인 기준 [-1, 0, 1]이 모두 1보다 크면 지뢰가 있다는 뜻이므로 "*"로 바꾸고 숫자를 하나씩 빼준다.
import sys
input = sys.stdin.readline
T = int(input())
dy = [-1, 0, 1]
def isMining(N, arr, y):
for d in dy:
ny = y + d
if 0 <= ny < N and arr[0][ny] <= 0:
return False
return True
for i in range (T) :
N = int(input())
arr = []
arr.append(list(map(int, input().rstrip())))
arr.append(list(input().rstrip()))
# * 부터 계산
for j in range(N):
if arr[1][j] == "*":
for d in dy:
ny = j + d
if 0 <= ny < N:
arr[0][ny] -= 1
# 숫자 하나씩 빼면서 계산
for j in range(N):
if isMining(N, arr, j):
arr[1][j] = "*"
for d in dy:
ny = j + d
if 0 <= ny < N:
arr[0][ny] -= 1
print(arr[1].count("*"))
36. 정육점(골4) 2258
• 가격은 오름차순, 무게는 내림차순으로 정렬한다. 적은 가격으로 많은 무게를 살수록 좋기 때문
• 이전 가격과 현재 가격이 같으면 이전 answer 값에 현재 가격을 더해주고, 뒤에 나오는 가장 작으면서 다른 가격과 answer를 비교하여 답을 구한다.
• 이전 가격과 현재 가격이 다르면 answer를 현재 가격으로 갱신하고 total이 M보다 크면 그 answer를 바로 출력한다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
arr.sort(key = lambda x: (x[1], -x[0]))
def buyMeat():
total = 0
answer = 0
for i in range(N):
total += arr[i][0]
if arr[i][1] == arr[max(0, i-1)][1]:
answer += arr[i][1]
if total >= M:
answer2 = 0
for j in range(i, N):
if arr[j][1] > arr[i][1]:
answer2 = arr[j][1]
break
if answer2:
return min(answer, answer2)
else:
return answer
else:
answer = arr[i][1]
if total >= M:
return answer
return -1
print(buyMeat())
37. 우체국(골4) 2141
• 숫자 범위가 커서 누적 평균으로 계산하면 오버플로우가 생긴다.
• f(x)를 최소화하는 x는 가중 중앙값이고, a1+a2+•••+ak >= 총 인구수/2를 만족하는 모든 xk가 답이 될 수 있다.
• 답이 여러 개면 가장 작은 값이 답이기 때문에 앞에서부터 탐색하며 좌우 인원수가 비슷해지는 시점(왼쪽 사람수가 전체 사람주의 절반 이상이 되는 시점)을 찾으면 된다.
import sys
input = sys.stdin.readline
N = int(input())
total = 0
arr = []
for i in range(N):
x, a = map(int, input().split())
total += a
arr.append([x, a])
total /= 2
arr.sort()
answer = 0
for i in range(N):
answer += arr[i][1]
if answer >= total:
print(arr[i][0])
exit()
38. 합(골3) 1132
• alphabet[알파벳(A는 0, B는 , ...)][자릿수합(101, 110, ...)]
• 이렇게 자릿수 합으로 우선순위를 미리 구해주면 A의 자릿수 합과 A가 가리키는 숫자를 곱해서 답을 구할 수 있다.
• (A*100 + B*10 + C)+(B*100 + C*10 + A)와 (A*101 + B*110 + C*11)이 같기 때문
• 내림차순으로 정렬한 후, 제일 작은 것부터 뒤에서 보면서 첫 자릿수가 아닌 것에 0을 대입한다.
• 예를 들어 [A, B, C, D, E, F, G, H, I, J] 순으로 되어 있는데 H, I, J가 다 첫 자릿수이면
그 다음으로 작은 G가 0이 되고, H, I, J가 3, 2, 1이 되는 것이다.
import sys
input = sys.stdin.readline
N = int(input())
arr = [list(input().rstrip()) for _ in range(N)]
# 자릿수 계산
alphabet = [[i, 0] for i in range(10)] # alphabet[알파벳][자릿수합]
first = []
for i in range(N):
first.append(ord(arr[i][0]) - ord("A"))
for j in range(len(arr[i])):
alphabet[ord(arr[i][j]) - ord("A")][1] += 10**(len(arr[i])-j-1)
# 우선순위 계산
alphabet.sort(key = lambda x: -x[1])
for i in range(9, -1, -1):
if alphabet[i][0] not in first:
alphabet.append(alphabet.pop(i))
break
# 최종 계산
answer = 0
for i in range(10):
answer += (9-i)*alphabet[i][1]
print(answer)
39. 순회강연(골3) 2109
• d 오름차순, p 내림차순으로 정렬한다.
• heap의 길이보다 d가 작으면 heap에 추가한다.
• heap이 찼지만 새로운 p가 heap의 루트보다 크면 루트를 제거하고 p를 넣는다.
반례
5
10 1
5 2
30 3
20 3
10 3
오답: 45
정답: 60 [10, 30, 20]
import sys
import heapq
input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
arr.sort(key = lambda x: (x[1], -x[0]))
h = []
for i in range(n):
current = len(h)
if current < arr[i][1]:
heapq.heappush(h, arr[i][0])
elif current == arr[i][1]:
first = heapq.heappop(h)
heapq.heappush(h, max(first, arr[i][0]))
print(sum(h))
40. 크게 만들기(골3)
2812
41. 코딩은 예쁘게(골3)
2879
42. 택배(골2) 8980
1에서 4로 20을 보낸다면, 2와 3에서도 20을 싣고 있는 상태다.
도착지를 기준으로 오름차순 해야한다. 먼저 내리는 것부터 계산해야한다.
도착지 오름차순으로 정렬된 입력 값에 따른 각 마을에서의 트럭 상태와 배송 상태를 알아보자.
[1, 2, 10]일 때, 트럭:[10, 0, 0, 0] , 배송:10
[1, 3, 20]일 때, 트럭:[30, 20, 0, 0] , 배송:30 //1과 2에 모두 20을 더한다.
[2, 3, 10]일 때, 트럭:[30, 30, 0, 0] , 배송:40
[1, 4, 10]일 때, 트럭:[40, 40, 10, 0] , 배송:50
[2, 4, 20]일 때, 트럭:[40, 40, 10, 0] , 배송:50 //2에서 더이상 짐을 실을 수 없다.
[3, 4, 20]일 때, 트럭:[40, 40, 30, 0] , 배송:70
import sys
input = sys.stdin.readline
N, C = map(int, input().split())
M = int(input())
arr = [list(map(int, input().split())) for _ in range(M)]
arr.sort(key = lambda x:(x[1]))
box = [0]*(N+1)
answer = 0
for a in arr:
weight = 10000
for j in range(a[0], a[1]):
weight = min(weight, a[2], C-box[j])
for j in range(a[0], a[1]):
box[j] += weight
answer += weight
print(answer)
43. 컵라면(골2)
1781
44. 컬러볼(골2) 10800
• [크기, 색] 오름차순으로 정렬한다.
• color와 size 배열에 해당 C와 S 값을 빼준다. 같은 색, 같은 크기는 못 잡기 때문
• 전 공과 색과 크기가 모두 같으면 음수가 나오므로 이때는 전 공의 답과 똑같이 출력한다.
import sys
input = sys.stdin.readline
N = int(input())
arr = [[i]+list(map(int, input().split())) for i in range(N)]
arr.sort(key = lambda x: (x[2], x[1]))
color = [0]*(N+1)
size = [0]*(2001)
answer = []
total = 0
for i in range(N):
idx, C, S = arr[i]
a = total - color[C] - size[S]
if i > 0 and C == arr[i-1][1] and S == arr[i-1][2]:
a = answer[i-1][1]
answer.append((idx, a))
total += S
color[C] += S
size[S] += S
answer.sort()
[print(a[1]) for a in answer]
45. 쓰레기 치우기(골2) 1736
• trash 배열에 쓰레기 위치(i, j)를 넣는다.
• 오른쪽과 아래쪽으로만 이동할 수 있기 떄문에 x와 y가 둘 다 크거나 같으면 같은 경로가 될 수 있는 쓰레기다.
• 현재 로봇 위치를 계속 갱신하고 쓰레기 주운 곳은 visited 처리하면서 계산한다.
import sys
input = sys.stdin.readline
# 입력
N, M = map(int, input().split())
arr = []
trash = []
for i in range(N):
n = list(map(int, input().split()))
for j in range(len(n)):
if n[j] == 1:
trash.append((i, j))
arr.append(n)
visited = [[0]*M for _ in range(N)]
# 이어지는 쓰레기를 차례대로 제거
answer = 0
while True:
x, y = -1, -1
for i in range(len(trash)):
if not visited[trash[i][0]][trash[i][1]]:
if trash[i][0] >= x and trash[i][1] >= y:
x, y = trash[i][0], trash[i][1]
visited[trash[i][0]][trash[i][1]] = 1
if x == -1 and y == -1:
break
answer += 1
print(answer)
46. 멀티탭 스케줄링(골1) 1700
댓글남기기