W1 .D3 - 그리디 문제 4~6

✏️문제4> 만들 수 없는 금액 🔥🔥

입력조건:첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다.(1<=N<=1,000)
둘째줄에는 각 동전의 화폐단위를 나타내는 N개의 자연수가 주어지며 각 자연수는 공백으로 구분한다.(화폐단위는 1,000,000이하의 자연수)
출력조건:첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력한다.

내 코드

CoinN=int(input())
CoinUnit=list(map(int, input().split()))
##print(CoinUnit)
CoinUnit.sort()

addVar=1
for i in CoinUnit:
    if i <= addVar:
        addVar+=i
    else:
        break
print(addVar)

feedback
생각보다 아이디어를 얻는데 시간이 많이 소요되었다.

---

✏️문제5> 볼링공 고르기🔥🔥

입력조건:첫째 줄에 볼링공의 개수 N 공의 최대무게 M이 공백으로 구분되거 각각 자연수 형태로 주어진다(1<=N<=1,000, 1<=M<=10)
출력조건:첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력한다.

내 코드

n,m= map(int,input().split())
k=list(map(int,input().split()))
##print(k)
count,overlapHap,answer=0,0,0
for num in range(1,m+1):
    ##print(k.count(num))
    overlap=k.count(num)


    if overlap>1:
        for ol in range(overlap-1,0,-1):
            overlap=overlap*(overlap-ol)

        overlapHap=int(overlap/2)
        ##print(overlapHap)

    count=count+overlapHap
    ##print(count)

hap=0
for i in range(1,n):
    hap=hap+i
##print(hap)
answer=hap-count
print(answer)

feedback

n, m = map(int, input().split())
data = list(map(int, input().split()))

# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11

for x in data:
    # 각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1

result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m + 1):
    n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    result += array[i] * n # B가 선택하는 경우의 수와 곱해주기

print(result)

문제를 꼼꼼히 읽지 않아서
공의 최대무게에 제한을 두지 않는 코드를 구성했는데..
제가 푼 문제 코드의 오류가 있어요.
아직 해결을 못해서 곧 해결해서 업로드 하겠습니다.(꼭 다시 풀고 싶어서 그대로 올려두었어요...)

---

✏️문제6> 무지의 먹방 라이브🔥🔥🔥

제한사항
1.food_times는 각 음식을 모두 먹는 데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
2.k는 방송이 중단된 시간을 나타낸다.
3.만약 더 섭취해야 할 음식이 없다면 -1을 반환한다.

내 코드

<다시한번 풀어볼게요>

feedback

import heapq

def solution(food_times, k):
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1

    # 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i + 1))  

    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수

    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정

    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1]) # 음식의 번호 기준으로 정렬
    return result[(k - sum_value) % length][1]