[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
• 스택의 top이 현재 숫자보다 큰 값이 나올 때까지 stack을 pop한 후 현재 숫자를 stack에 추가한다.
• stack이 비어있거나 지운 숫자가 K개가 되었다면 바로 현재 숫자를 stack에 추가한다.
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
num = input().rstrip()
stack = []
cnt = 0
for n in num:
while True:
if len(stack) == 0 or stack[-1] >= n or cnt == K:
break
stack.pop()
cnt += 1
stack.append(n)
print(''.join(stack[:N-K]))
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
댓글남기기