2021. 7. 20. 23:57ㆍ코딩테스트/백준
2839번: 설탕 배달
3kg, 5kg 짜리 설탕 봉지를 최대한 적게 이용하여 Nkg을 만들기
큰 것 부터 확인 -> 그리디
풀이:
1. N이 5로 나누어 떨어지는지 확인 -> 안되면 N = N-3, ans += 1
2. 1번 무한 반복 -> N이 5로 나누어 떨어지면 ans += N/5
N = int(input())
ans = 0
while N >= 0:
if(N%5==0):
ans += (N / 5);
print(int(ans))
break
else:
N -=3
ans += 1
else:
print(-1)
11399번: ATM
N명의 ATM사용자 각각 이용하는 시간이 다름, 각 사람이 기다리는 시간의 합의 최소를 구하여라.
Ex) [3, 1, 4, 3, 2]
순서대로 -> 3 + (3+1) + (3+1+4) + ... = 39
그리디(정렬 후) -> 1 + (1+2) + (1+2+3) + ... = 32
풀이:
1. 주어진 시간 오름차순 정렬
2.
a1 +
a1 + a2 +
a1 + a2 + a3 +
...
가로 합 : O(n^2)세로 합 : O(n)
N = int(input())
P = list(map(int, input().split()))
P.sort()
ans = 0
for i in range(N):
ans += P[i]*(N-i)
print(ans)
2812번: 크게 만들기
N자리 숫자가 주어졌을 때, 숫자 K개를 지워서 만들 수 있는 가장 큰 수를 구하기
Ex)
4 2
1924 -> 94
풀이:
1. 숫자의 크기는 높은 자리의 수가 결정한다. -> 높은 자리부터 순차적으로 큰 수를 택하는 그리디 알고리즘
2. 주어진 수를 ans에 하나씩 옮기면서 주어진 숫자와 비교
3. ans에 들어간 최상위 숫자(높은 자리의 수) < 주어진 숫자의 최상위 숫자(높은 자리의 수) : ans.pop(), ans.append(num[i])
4. 2,3을 N번 반복하거나 K번 뺐으면 종료
N, K = list(map(int,input().split()))
num = list(input())
ans = []
K_ = K
for i in range(N):
while K > 0 and len(ans) > 0:
if ans[-1] < num[i]:
ans.pop()
K -= 1
else:
break
ans.append(num[i])
for i in range(N-K_):
print(ans[i],end='')
#print(*ans,sep='')
2212번: 센서
N개의 센서를 모두 커버할 수 있는 K의 집중국의 센서 감지 거리의 합의 최소 구하기
풀이:
1. 수직선에 나타내었을 때 센서간의 거리가 순서대로 보임 -> 센서간의 거리만 포함하는 리스트
2. 센서간의 거리를 나타내는 리스트 내림차순 정렬
3. 거리를 하나 뺄 때 마다 집중국의 개수는 한 개 씩 늘어남 -> K개의 집중국이 있을때는 K-1개 빼면됨
4. sum(sSub[K-1:])
N = int(input())
K = int(input())
s = list(map(int,input().split()))
s.sort()
sSub = [s[i+1] - s[i]for i in range(len(s)-1)]
sSub.sort(reverse=True)
print(sum(sSub[K-1:]))