4/6 Coding Test

✅ 문제 풀이 - BOJ (Greedy)

🎈 13164 행복 유치원

n명의 유치원생들을 일렬로 키 순대로 줄세우고 k개의 조로 나누려고 한다.
나누어진 조에 따라 단체 티를 맞추려고 할때, 단체 티셔츠 비용은 조에서 가장 키 큰 원생과 키가 가장 작은 원생의 키 차이만큼 들 때, 최소 비용을 구하는 문제

• 입력: 유치원생 수 n, 조 수 k, 원생들의 키를 오름차순으로 정렬된 배열

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
height = list(map(int, input().split()))

answer = []
for i in range(n-1):
    answer.append(height[i+1] - height[i])
answer.sort()
print(sum(answer[:n-k]))

< 풀이 과정 >
n, k, height를 입력값으로 두고 for문으로 n-1까지 인덱스를 i로 둔다.
결국 조를 어떻게 만들든 앞 뒤 원생의 키 차이를 answer에 저장을 하여 n-k까지의 인덱스 기준 합을 구하면 된다. 가장 키가 큰 원생은 따로 조를 구성해두어야만 비용을 최소화할 수 있다.

🎈 19939 박 터뜨리기

n개의 공을 k개의 바구니에 담으려고 하는데 나눠 담기에는 규칙이 필요하다.

• n개의 공을 k개의 바구니에 빠짐없이 나누어 담는다
• 각 바구니에는 1개 이상의 공이 있어야 한다.
• 각 바구니에 담긴 공의 개수는 달라야 한다.
• 공이 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 개수 차이가 최소가 되어야 한다.

결론적으로, 규칙을 만족하며 최소 공의 개수 차이를 구하는 문제이고, 나눠 담을 수 없는 경우 -1을 출력한다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
ball = [i for i in range(1, n+1)]

min_ball = k * (k+1) / 2
if min_ball > n:
    print(-1)
elif (n-min_ball) % k == 0:
    print(k-1)
else:
    print(k)

< 풀이 과정 >
k개의 바구니에 서로 다른 공의 개수를 넣으려면 필요한 공의 개수는 최소 k(k+1)/2이고 해당 값을 min_ball 변수로 둔다.

• 이후 min_ball이 n보다 크면, 가능한 경우의 수가 없으므로 -1을 출력한다.
• 만일 n - min_ball이 k의 배수라면 k-1을 출력한다. 어차피 공의 개수가 다르게 바구니에 넣는데 각 공을 바구니에 넣어준 것들에 합이 k라면 어차피 k개 공 - 1개 공 넣은 바구니의 개수차이와 동일하기 때문이다. ex) n=20, k=5, [2,3,4,5,6]
• 나머지의 경우 k만큼 차이가 나게 된다

🎈 21758 꿀 따기

장소 개수 n과 각 장소별 꿀의 양이 주어진다.
구하고자 하는 것은 다음과 같다.

• 서로 다른 두 장소에 벌이 위치하고, 또 다른 장소에 벌통이 있다.
• 두 마리가 모두 지나간 장소에서는 두마리 모두 표시된 양만큼 꿀을 딴다.
• 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

최종적으로 각 벌이 딸 수 있는 벌의 양은 자신 위치 제외 ~ 벌통위치까지의 꿀 양의 합일 때, 최대 채굴가능한 꿀의 양을 구하는 문제

import sys
input = sys.stdin.readline

n = int(input())
honey = list(map(int, input().split()))
result = []
result.append(honey[0])
for i in range(1, n):
    result.append(result[i-1] + honey[i])
answer = 0
# case1 꿀통 오른쪽 끝, 왼쪽 끝 벌, i번째 벌 위치
for i in range(1, n-1):
    answer = max(answer, result[n-1] - honey[0] - honey[i] + result[n-1] - result[i])
# case2 꿀통 왼쪽끝, i번째 벌, 오른쪽 끝 벌 위치
for i in range(1, n-1):
    answer = max(answer, result[n-2] - honey[i] + result[i-1])
# case3 꿀통 가운데, 왼쪽 끝, 오른쪽 끝 벌 위치
for i in range(1, n-1):
    answer = max(answer, result[n-2] - honey[0] + honey[i])
print(answer)

< 풀이 과정 >
꿀벌이 이동한 만큼의 지나온 꿀 양의 합을 계산하기 위해 누적합을 우선 리스트로 꾸며준다.
result로 주어진 honey의 첫번째 인덱스 값을 넣고 for문으로 1~n까지 반복하며 result를 result[i-1] + honey[0]으로 두어 누적합을 만들어준다.

그 이후 다음 3가지 비교를 거쳐야만 최대 값을 계산할 수 있다.

• 1. 꿀통 오른쪽, 왼쪽 끝과 i번째에 각각 꿀벌 위치
     왼쪽 끝에 위치한 벌이 벌어오는 양 : result[n-1] - honey[0] - honey[i]
     i번째 위치한 벌이 벌어오는 양 : result[n-1] - result[i]
• 2. 꿀통 왼쪽, 오른쪽 끝과 i번째에 각각 꿀벌 위치
     오른쪽 끝에 위치한 꿀벌이 벌어오는 양 : result[n-2] - honey[i]
     i번째 위치한 꿀벌이 벌어오는 양 : result[i-1]
• 3. 꿀통 가운데, 왼쪽 끝, 오른쪽 끝에 각각 꿀벌 위치
     좌우 끝 원소 제거하고 합 : result[n-2] - honey[0]
     꿀통 위치 중복 : honey[i]

각각 answer = 0으로 둔 이후, answer와 해당 위치의 합을 비교하여 max값 뽑아내는 문제