당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.
N=1,260일때 예시
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
array = [500,100,50,10]
for coin in array:
count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)
(이코테 그리디 실전문제 4번)
N, K = map(int, input().split())
count = 0
while(True):
if N==1:
print(count)
break;
if(N%K != 0 ):
count += 1
N -= 1
else:
count += 1
N //= K
N이 K의 배수가 아닐때, count를 1씩 증가하고 N에서 1을 뺐다. 이를 반복하여 N이 K의 배수가 되도록 하고, 최종적으로 N이 1일 될 때 증가한 count값을 출력하면서 while문을 빠져나오도록 하였다.
내가 푼 풀이는 책과 유튜브에서 설명하듯이 일일이 1씩 빼어 문제를 해결하는 방식이다. 하지만, N이 100억 이상의 큰 수가 되는 경우 빠르게 동작하기 위해 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식의 소스코드도 고려했어야 한다고 생각한다.
n, k = map(int, input().split())
result = 0
while True:
#N이 K로 나누어 떨어지는 수가 될 때까지 빼기
target = (n//k)*k
result += (n - target) #1을 빼는 연산 횟수
n = target
#N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
#K로 나누기
result += 1
n //=k
#마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)
print(result)
(이코테 그리디 기출문제 2번)
"""
아이디어
주어진 문자열 앞에서부터 +와 x연산을 한후 더 큰 값이 나온걸 통과시킨다.
"""
S_input = input()
#문자를 입력받아 char하나를 int형으로 변환해 리스트에 넣어준다.
S = [int(i) for i in S_input]
result = S[0] #첫 비교대상은 첫번째 인자
for i in range(1,len(S)):
if(result + S[i] <= result * S[i]):
result *= S[i]
else:
result += S[i]
print(result)
주어진 문자열을 하나하나 분리후 int형으로 만들어 리스트에 넣어준다.
첫 result를 첫번째 인자로 넣어주고, 앞에서부터 순서대로 +와 x 연산을 진행하여 더 큰 값이 나오는 것을 통과시킨다.
이를 for문을 통해 반복해준다.
data = input()
#첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])
for i in range(1, len(data)):
# 두 수 중에서 하나라도 '0'혹은 '1'인 경우, 곱하기보다는 더하기 수행
num = int(data[i])
if num <= 1 or result <=1 :
result += num
else:
result += num
print(result)
(이코테 그리디 기출문제 1번)
2 3 1 2 2
"""
공포도를 오름차순 한 후, 그룹을 만들 수 있는 조건에 맞는지 부합하는지 확인한다.
"""
N = int(input())
fears = list(map(int, input().split()))
fears.sort()
result = 0 #총 그룹의 수
count = 0 #현재 그룹에 포함된 모험가의 수
for i in fears: #공포도를 낮은 것부터 하나씩 확인하며
count += 1 # 현재 그룹에 해당 모험가를 포함시키기
if count >= i: #현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
result += 1 # 총 그룹의 수 증가시키기
count = 0 #현재 그룹에 포함된 모험가의 수 초기화
print(result)
"또한, 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다." 라는 문장을 신경쓰느라 오히려 해결법을 찾는데 어려움을 겪었던 것 같다. 단순하게 오름차순 정렬 후, 그룹을 만들어 현재 그룹에 포함된 모험가의 수와 들어오는 모험가의 공포도를 비교하여 만든 그룹과 멤버 모두를 고려하여 만듬 그룹의 max치는 같다는걸 생각하지 못했다.
(이코테 그리디 실전문제 2번)
'''
큰 수의 법칙 : 다양한 수로 이루어진 배열이 있을 때,
주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.
(단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 업는 것이 이 법칙의 특징이다.
'''
#배열의 크기 N, 더해지는 횟 수 M, K번 초과해서 연속으로 더할 수 없음.
N,M,K = map(int, input().split())
print(N,M,K)
numbers = list(map(int, input().split()))
#print(numbers)
#정렬하기
numbers.sort(reverse=True) #6 5 4 4 2
result = 0
repeat = M//(K+1)
plus = M%(K+1)
print(repeat,plus)
for i in range(repeat):
for j in range(K):
result += numbers[0]
result += numbers[1]
result += (numbers[0]*plus)
print(result)
배열을 정렬하여 가장 큰 수와 두번째로 큰 수를 구한다. 가장 큰 수는 K번 두번째로 큰수는 1번 반복되는데, M//(k+1)번 반복하는 규칙이 있다. 그리고 가장 큰 수가 M%(K+1)번 추가로 더해진다. 이를 코드화한다.
2~3번 풀어본 문제인데 풀때마다 항상 헷갈린다. 문제를 그대로 받아들이고 구현하는 것 뿐만아니라 그 속의 새 규칙을 찾아 풀어보자는 생각 또한 항상 가져야 한다고 느끼게 해준 문제이다.
(이코테 그리디 실전문제 3번)
N, M = map(int, input().split())
cards = []
row = []
for i in range(N):
row = list(map(int,input().split()))
row.sort()
cards.append(row)
def findBigNum(cards,N):
numMax = cards[0][0]
for i in range(N):
if (cards[i][0] > numMax):
numMax=cards[i][0]
# print(cards[i][0])
return numMax
print(findBigNum(cards,N))
각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는다.
min(), max()함수를 이용해서 풀 수도 있다.
(이코테 그리디 기출문제 3번)
S = input()
action0 = 0 # 모두 0으로 바꾸는 경우
action1 = 0 # 모두 1로 바꾸는 경우
# 첫 번째 원소에 대해 처리
if S[0] == '1':
action0 += 1
else:
action1 += 1
# 두 번째 원소부터 검사!
for i in range(len(S)-1):
if S[i] != S[i+1]:
if S[i+1] == '1':
action0 += 1
else:
action1 += 1
print(min(action0, action1))
모두 0으로 바뀌는 경우와 모두 1로 바뀌는 경우를 모두 구한 후, min함수를 이용해 더 작은 값을 출력한다.
case1) 000 11 00 -> 000 00 00
case2) 111 00 11 -> 111 11 11
첫 번째 원소가 1일 경우를 먼저 처리해준다. (비교대상이 없기 때문에)
앞에 1이 나오면 모두 0으로 바꾸는 action0이 증가하고,
0이 나오면 모두 1로 바꾸는 action1이 증가한다.
두 번재 원소부터는 다음 원소와 값이 다를 때 1이 오면 (01) action0을 증가시키고 0이 오면(10) action1을 증가시킨다.
이후 action0과 action1중 최소값을 출력한다.
(이코테 그리디 기출문제 4번)
N = int(input())
coins = list(map(int,input().split()))
coins.sort()
target = 1
for x in coins:
if target < x:
break
target += x
print(target)
주어진 동전 배열을 정렬한후, 작은 동전부터 하나씩 target값과 비교한다.
(이코테 그리디 기출문제 5번)
N, M = map(int,input().split())
bowling = list(map(int, input().split()))
count = 0
for i in range(1,N+1):
if bowling.count(i) >= 2:
a = bowling.count(i)
count += (a*(a-1))/2
print(((N*(N-1))/2)-count)
food_times = [3,1,2]
k=6
for i in range(1,k+1):
index = i%len(food_times)
i_list = []
if index == 0:
index = len(food_times)
if food_times[index-1] == 0:
food_times[index%len(food_times)] -= 1
i_list.append(index%len(food_times)+1)
else:
food_times[index-1] -= 1
i_list.append(index)
# print(food_times)
# print(i_list)
print(i_list[0])