이것이 코딩테스트다 chapter 11 그리디 문제 4-6번

1. 만들 수 없는 금액

체감 난이도 🤢🤢🤢

정답 코드

n = int(input())
data = list(map(int, input().split()))
data.sort()
a = 1

for x in data:
    if a < x:
        break
    a += x

print(a)

과정

아이디어를 생각하는것이 중요한 문제인것같다.

1. 1 1 1 1
   출력 5
   -> 다 더한거에서 +1이 최소값
   조건 왼쪽부터 차례로 더하는데 오른쪽의 값이 왼쪽에 더한 값보다 작거나 같다.

2. 1 2 3 4
   출력 11
   -> 다 더한거에서 +1이 최소값
   조건 왼쪽부터 차례로 더하는데 오른쪽의 값이 왼쪽에 더한 값보다 작거나 같다.

3. 1 1 4 6
   출력 3
   1+1+1<4 이므로 1+1+1은 3이다.

규칙을 생각해보자.
1. 가장 기본적인 최소값은 1이다. (a=1)
2. 왼쪽부터 차례로 더해 오른쪽 값보다 작거나 같아야한다.
3. 배열 모두 2번을 만족하면 모두 더한값의 +1이 최소값이다.

볼링공 고르기

체감 난이도 🤢

정답코드

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

for i in range(len(data)):
    for j in range(i, len(data)):
        if data[i] != data[j]:
            result += 1

print(result)

과정

그냥 이중 반복문을 돌려 다르면 result+=1를 해주었다.
이중 반복문은 안쓰는게 좋은데...더 이상 생각하기 귀찮다..!

무지의 먹방 라이브

체감 난이도 🤢🤢🤢🤢🤢(못품)

틀린코드

def solution(food_times, k):
    count = 0
    if sum(food_times) <= k:
        return -1

    food_times = [f - k // len(food_times) for f in food_times]
    k = k - k // len(food_times) * len(food_times)

    for i in range(len(food_times)):
        if food_times[i] <= 0:
            k -= food_times[i]
            count += 1

    if k >= len(food_times) - count:
        for i in range(len(food_times)):
            if food_times[i] > 0:
                food_times[i] -= 1
                k -= 1

    for i in range(len(food_times)):
        if k == 0:
            if food_times[i] > 0:
                return i + 1
            if food_times[i] == 0:

        if food_times[i] > 0 and k>0:
            food_times[i] -= 1
            k -= 1
            if food_times[i] > 0 and k == 0:
                return i + 1




    return -1


a = solution([3,1,2],5)
print(a)

과정

진짜 여러가지 생각을 해봤다...
위의 코드는 이런 아이디어다.
1. 배열을 모두 더해서 k와 같거나 작으면 return -1

2. k//len(food_times) 는 모든 배열에 빼줘야하는 수이다. (3,1,2 모두 1을 빼줘야한다 (k=5-3))
   반복한 횟수만큼 k를 줄인다.
   food_times = [f - k // len(food_times) for f in food_times]
   k = k - k // len(food_times) * len(food_times)

3. 빼주다보면 음수인 부분이 생긴다.
   4,3,2,1 / 9
   9//4=2
   4-2,3-2,2-2,1-2 -> 2,1,0,-1
   이 음수를 처리해줘야한다.
   음수부분을 count에 집어넣어
   for i in range(len(food_times)):
   if food_times[i] <= 0:
   k -= food_times[i]
   count += 1
   음수 값만큼 다시 k에 더한다.

4. k와 배열길이-count를 비교해서 k가 크면 한번더 배열을 돌린다.
   왜냐면 2 3 0 0 0 0 3 인데 5번이 남은 경우 배열을 두번 돌려야하기 때문에...

5. 나머지 k 만큼 다시 배열을 돌린다...

위 아이디어는 우선 해결 못한 아이디어이다...
하지만 혹시 다음에 위 아이디어로 해결해볼 수 있도록 정리해보았다.

정답 코드

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]

정답코드 분석

참고문서

이것이 코딩테스트다 책