2021_07_20 백준 문제 풀이(2839,11399, 2812, 2212)

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:]))