01-3. 그리디 알고리즘 문제풀이

📝문제4. 만들 수 없는 금액

- 문제

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있다. 이때 N개의 동전을 이용해 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성해라.

예를 들어, N=5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정하자. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다.
또 다른 예로, N=3이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위) 동전이라고 가정하자. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원이다.

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

- 나의 코드💻

# 조합을 사용하기 위해 라이브러리를 불러옴
from itertools import combinations

n = int(input())
m = list(map(int, input().split()))
m.sort()  # 오름차순 정렬

# 조합을 이용해 주어진 동전들로 만들 수 있는 모든 금액에 관한 리스트 만들기
comb = []
for i in range(1, len(m)+1): # len(m)+1의 이유를 잘 모르겠다
    c = (list(combinations(m, i)))
    for x in range(0, len(c)):
        comb.append(sum(c[x]))

comb = list(set(comb))  # 중복 제거
comb.sort()  # 오름차순 정렬

k = 1  # 최솟값
# for문을 이용해 리스트 내에서 존재하지 않는 최솟값 찾기
for i in comb:
    if k == i:
        k = i
        k += 1
    else:
        break
print(comb)
print(k)

- 정답 코드💻

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

target = 1
for x in data:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x
    
# 만들 수 없는 금액 출력
print(target)

- 비교 분석📖

조합 라이브러리를 인터넷에 검색해보고, 이런저런 시도 끝에 답이 출력되는 코드를 작성할 수 있었다. 나는 조합을 이용해 모든 경우의 수를 구해 리스트에 넣었다. 그 후 반복문을 이용해 리스트에 없는 수의 최솟값을 찾았다. 반면 정답 코드는 for x in data라는 반복문 하나만 사용해 해결하는 아주 간단한 방법이었다. 이 부분의 코드를 이해하는 것이 조금 힘들었고, 더 간결한 코드를 작성해야겠다는 생각이 들었다.

그런데 글을 쓰는 지금, for i in range(1, len(m)+1) 부분에서 왜 len(m)에 1을 더하는지 갑자기 이해가 안간다. 작성할 때는 분명히 이유가 있었던 것 같은데 갑자기 헷갈린다. +1을 하게 되면 그 밑줄에서 조합을 할 때 리스트의 길이보다 더 많은 수로 조합을 해야 하는 것 같은데, 아닌가,,? 어디서부터 생각이 꼬였는지 잘 모르겠다.. 또한 입출력 예시가 하나뿐이라 제대로 구현했는지도 잘 모르겠다..
-> for i in range(a, b)에서 a부터 b-1까지 반복한다는 사실을 잊고 있었다..

---

📝문제5. 볼링공 고르기

- 문제

A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성해라.

예를 들어 N이 5이고, M이 3이며 무게가 차례대로 1, 3, 2, 3, 2일 때 각 공의 번호가 차례대로 1부터 5번까지 부여된다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같다.
(1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번)
결과적으로 두 사람이 공을 고르는 경우의 수는 8가지이다..

입력 조건 : 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어진다. 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다.
출력 조건 : 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력한다.
입력 예시1 : 5 3 / 1 3 2 3 2
출력 예시1 : 8
입력 예시2 : 8 5 / 1 5 4 3 2 4 5 2
출력 예시2 : 25

- 나의 코드💻

from itertools import combinations

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

# 조합을 이용해 두 사람이 공을 고르는 모든 경우의 수 구하기
# 조합을 이용하면 각기 다른 공을 고르도록 할 수 있다
comb = list(combinations(k, 2))

# 같은 무게의 공이 여러 개 있어도 서로 다른 공으로 간주한다고 해서
# 윗문제와 달리 set을 이용해 중복을 제거하지 않았다. 

count = 0
for i in range(0, len(comb)):
    # 두 사람이 같은 무게의 공을 고르는 횟수 세기
    if comb[i][0] == comb[i][1]:
        count += 1

# 두 사람이 공을 고르는 경우의 수에서 같은 무게의 공을 고르는 경우의 수를 뺐다.
num = len(comb) - count
print(num)

- 정답 코드💻

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

print(result)

- 비교 분석📖

나는 정답 코드와 달리 입력 받은 n, m을 활용하지 않았다. 이런 값들을 입력받을 때는 이를 활용하는 방법을 떠올려봐야겠다.

---

📝문제6. 무지의 먹방 라이브

- 문제

https://programmers.co.kr/learn/courses/30/lessons/42891?language=python3
이 링크를 통해 문제를 풀어야 한다고 한다.

- 나의 코드💻

😥

- 정답 코드💻

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]

- 비교 분석📖

해결하지 못했다. 내가 우선순위 큐는 개념으로만 공부하고 코드로 실질적으로 작성해본 적은 없어서 이해하기 조금 어렵게 느껴진다. 주말에 시간을 내어 우선순위 큐와 lambda의 개념과 그 활용법, 파이썬에서 어떻게 적용하는지 등을 공부해봐야겠다.. 😂 이제 무지가 좀 싫어질 것 같다..

---

#. 보완할 점🔨

---

문제 출처 : 이것이 코딩 테스트다 with 파이썬(나동빈)