W1.D4- 백준 (11399번, 11047번, 2839번)

문제 11399 🔥🔥

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력조건 :첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
출력조건:첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

입력받은 시간 오름차순으로 정렬->합 계산=최솟값

내 코드

people = int(input())
array = list(map(int, input().split()))
num = 0
array.sort()
for i in range(people):
    for j in range(i + 1):
        num = num+array[j]
print(num)

feedback
문제를 잘 이해하자
문제를 이해하는데 시간이 꽤나 걸렸다....

---

문제 11047 🔥🔥

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력조건:첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력조건:첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

최솟값구하기->가장 큰 단위 동전으로 나누기

내 코드

n,k = map(int, input().split()) 
coins = [] 
count = 0 
for _ in range(n): 
	coins.append(int(input())) 
for i in range(len(coins)-1,-1,-1): 
	count += k // coins[i] 
	k = k - k // coins[i] * coins[i] 
print(count)

feedback

• 추가)
  내림차순을 이용한 방법도 해보기

...중략 

coins.sort(reverse=True)
#동전 개수 구하기
for i in coins:
  if k==0: break
  count+=k//i
  k%=i
print(count)

---

문제 2839🔥

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력조건:첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력조건:상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

5이상& 3,4 일때 구분하기, 5이상이면 5로 나누고 3으로 나누기,
주의: 5의 배수 아닌 3의 배수일때도 구해야함

내 코드

N = int(input())
FiveKG = int(N/5)
N = N % 5
ThreeKG = 0
while FiveKG>=0:
    if N%3 == 0 :
        ThreeKG = int(N/3)
        N = N%3
        break
    FiveKG -= 1
    N=N+5
if N == 0:
    print(FiveKG+ThreeKG)
else:
    print(-1)

feedback

다양한 답을 찾아보니 for문을 이용한 해답도 있었다.
다양하게 풀어보자

보완할 점

좀더 다양한 풀이방법을 보고 익히기
문제를 꼼꼼히 읽기

간단한 문제에 비해서 시간이 꽤나 걸렸다...
열공하자💪🏼