ATM

 
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB 94138 63582 50968 68.035%

문제

인하은행에는 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)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

n = int(input())  # 18
p = list(map(int, input().split()))
temp = sorted(p)

result = 0; temp1 = 0

for x in temp:
  result += x
  temp1  += result

print(temp1)

'CoTe > 그리디' 카테고리의 다른 글

[그리디]2839  (0) 2023.07.13
[그리디] 2720번  (0) 2023.06.01
[그리디] 10162번  (0) 2023.06.01
[이코테] 1일 될 때까지  (0) 2023.05.04
[이코테]숫자 카드 게임  (0) 2023.05.04

 

설탕 배달 다국어

한국어   
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB 290948 106820 80774 36.491%

문제

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

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

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

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

    1. 첫째 줄에 N kg이 들어오므로 N의 변수를 받은 뒤, 수를 세기 위한 count 변수도 함께 만든다.
    2. 봉지의 최소 개수를 출력해야 하므로, While 반복문을 사용하여 총 무게가 0kg보다 작거나 같을 때 까지 반복한다.
    3. if 문을 통해 %을 사용하여 5로 나눠 0 이 된다면 count에 5를 나눈 숫자를 더해주고, 나누어 떨어지지 않는다면 총 무게에 3을 빼고 count에 1을 더한다.
    4. else 구문으로는 0으로 나누어 떨어지지 않을 시 -1을 출력하도록 한다.
n = int(input())  # 18
count = 0

while n >= 0:
  if n % 5 == 0:
    count += int(n // 5)
    print(count)
    break

  n -= 3
  count += 1

else:
  print(-1)

'CoTe > 그리디' 카테고리의 다른 글

[그리디]11399  (0) 2023.07.13
[그리디] 2720번  (0) 2023.06.01
[그리디] 10162번  (0) 2023.06.01
[이코테] 1일 될 때까지  (0) 2023.05.04
[이코테]숫자 카드 게임  (0) 2023.05.04

세탁소 사장 동혁 성공다국어

한국어   
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB 13704 9996 9063 74.074%

문제

미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다.

동혁이는 리암에게 실망했다.

리암은 거스름돈을 주는 것을 자꾸 실수한다.

심지어 $0.5달러를 줘야하는 경우에 거스름돈으로 $5달러를 주는것이다!

어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성하려고 하지만, 디아블로를 하느라 코딩할 시간이 없어서 이 문제를 읽고 있는 여러분이 대신 해주어야 한다.

거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상 $5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어, $1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)

출력

각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.

예제 입력 1 복사

3
124
25
194

예제 출력 1 복사

4 2 0 4
1 0 0 0
7 1 1 4
t = int(input())
a = b = c = d = 0

# 0.25 0.10 0.05 0.01
for _ in range(t):
  n = int(input())
 
  a = n // 25
  b = (n % 25) // 10
  c = ((n % 25) % 10) // 5
  d = (((n % 25) % 10) % 5) // 1
  # a, b, c, d = [int(x) for x in [a, b, c, d]]
  print(a, b, c, d)

'CoTe > 그리디' 카테고리의 다른 글

[그리디]11399  (0) 2023.07.13
[그리디]2839  (0) 2023.07.13
[그리디] 10162번  (0) 2023.06.01
[이코테] 1일 될 때까지  (0) 2023.05.04
[이코테]숫자 카드 게임  (0) 2023.05.04

전자레인지 성공서브태스크

 
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 64 MB 30952 18379 15846 60.064%

문제

3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다.

냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A, B, C를 누른 횟수의 합은 항상 최소가 되어야 한다. 이것을 최소버튼 조작이라고 한다.

만일 요리시간이 100초라고 하면(T=100) B를 1번, C는 4번 누르면 된다. 이와 다르게 C를 10번 눌러도 100초가 되지만 이 경우 10번은 최소 횟수가 아니기 때문이 답이 될 수 없다. 이 경우 B 1번, C 4번, 총 5번이 최소버튼 조작이다. 그리고 T=234와 같이 3개의 버튼으로 시간을 정확히 맞출 수 없는 경우도 있다.

여러분은 주어진 요리시간 T초를 맞추기 위한 최소버튼 조작 방법을 구하는 프로그램을 작성해야 한다.

입력

첫 번째 줄에는 요리시간 T(초)가 정수로 주어져 있으며 그 범위는 1 ≤ T ≤ 10,000 이다.

출력

여러분은 T초를 위한 최소버튼 조작의 A B C 횟수를 첫 줄에 차례대로 출력해야 한다. 각각의 횟수 사이에는 빈 칸을 둔다. 해당 버튼을 누르지 않는 경우에는 숫자 0을 출력해야한다. 만일 제시된 3개의 버튼으로 T초를 맞출 수 없으면 음수 -1을 첫 줄에 출력해야 한다.

서브태스크

번호배점제한
1 30 T ≤ 60
2 30 T ≤ 300
3 40 T ≤ 10,000

예제 입력 1 복사

100

예제 출력 1 복사

0 1 4

예제 입력 2 복사

189

예제 출력 2 복사

-1
n = int(input())
a = b = c = 0

if n % 10 != 0:
  print(-1)
else:
  a = n // 300
  b = (n % 300) // 60
  c = ((n % 300) % 60) // 10

print(a, b, c)

'CoTe > 그리디' 카테고리의 다른 글

[그리디]2839  (0) 2023.07.13
[그리디] 2720번  (0) 2023.06.01
[이코테] 1일 될 때까지  (0) 2023.05.04
[이코테]숫자 카드 게임  (0) 2023.05.04
[이코테] 큰 수의 법칙  (0) 2023.04.28 

# N, M, K를 공백으로 구분하여 입력
n, m = map(int, input().split())  # m번 많큼 반복 더하고 k만큼 번갈아
count = 0

while 1:
  if n == 1:
    break
  else:
    if n % m == 0:
      remain = n // m  # 17 4
      n = remain
      count += 1
    else:
      n -= 1
      count += 1
      
print(count)
#solution
# N, M, K를 공백으로 구분하여 입력
n, k = map(int, input().split())  # m번 많큼 반복 더하고 k만큼 번갈아
result = 0

while 1: # 25 5 17 4
  # (N==K로 나누어떨어지는 수)가 될 때까지 1씩 빼기
  target = (n//k) * k
  result += (n - target)
  n = target
  # N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
  if n < k:
    break
  # K로 나누기
  result += 1
  n //= k
# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)
print(result)

'CoTe > 그리디' 카테고리의 다른 글

[그리디] 2720번  (0) 2023.06.01
[그리디] 10162번  (0) 2023.06.01
[이코테]숫자 카드 게임  (0) 2023.05.04
[이코테] 큰 수의 법칙  (0) 2023.04.28
[이코테]그리디(탐욕법)  (0) 2023.04.28 

# N, M, K를 공백으로 구분하여 입력
n, m = map(int, input().split())  # m번 많큼 반복 더하고 k만큼 번갈아
temp = []
for _ in range(n):
  data = list(map(int, input().split()))
  temp.append(min(data))

print(max(temp))
# solution
n, m = map(int, input().split())   
result = 0
for _ in range(n):
  data = list(map(int, input().split()))
  minx = min(data)
  result = max(result, minx)

print(result)

'CoTe > 그리디' 카테고리의 다른 글

[그리디] 2720번  (0) 2023.06.01
[그리디] 10162번  (0) 2023.06.01
[이코테] 1일 될 때까지  (0) 2023.05.04
[이코테] 큰 수의 법칙  (0) 2023.04.28
[이코테]그리디(탐욕법)  (0) 2023.04.28 

# N, M, K를 공백으로 구분하여 입력
n, m, k = map(int, input().split()) # m번 많큼 반복 더하고 k만큼 번갈아
data = list(map(int, input().split()))
data.sort()

first = data[n-1]
second = data[n-2]

result = 0

while True:
  for i in range(k):
    if m == 0:
      break
    result += first
    m -= 1
  if m == 0:
    break
  result += second
  m -= 1

print(result)  
# 5 8 3
# 2 4 5 4 6

'CoTe > 그리디' 카테고리의 다른 글

[그리디] 2720번  (0) 2023.06.01
[그리디] 10162번  (0) 2023.06.01
[이코테] 1일 될 때까지  (0) 2023.05.04
[이코테]숫자 카드 게임  (0) 2023.05.04
[이코테]그리디(탐욕법)  (0) 2023.04.28
  • 현재 상황에서 지금 당장 좋은 것만 고르는 방법(다만, 나중에 미칠 영향을 고려하지 않는다)
  • 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야한다.
더보기

 

n = 1260
count = 0

coin = [500, 100, 50, 10]

for i in coin:
  count += n // i # 정수만 취함
  n %= i # 나머지
print(count)

 

  • 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분한다.
  • 하지만 거스름돈 문제에서 '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것과 같이, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적.
  • 그리디로 문제를 해결 했을 때 정당한지 검토하 해야함

'CoTe > 그리디' 카테고리의 다른 글

[그리디] 2720번  (0) 2023.06.01
[그리디] 10162번  (0) 2023.06.01
[이코테] 1일 될 때까지  (0) 2023.05.04
[이코테]숫자 카드 게임  (0) 2023.05.04
[이코테] 큰 수의 법칙  (0) 2023.04.28

+ Recent posts

티스토리툴바