그리디 문제

모험가 길드

모험을 떠나는데 공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날수 있도록 규정 .

최대 몇개의 모험가 그룹을 만들수 있는가

N=5 이고 모험가의 공포도가 다음과 같다면

2 3 1 2 2

그룹 1 은 1,2,3 그룹 2는 2, 2

나의 풀이

# 입력 : 모험가의 수 n  ,각 모험가의 공포도 
# 출력 : 여행을 떠날수 있는 그룹수 최댓값 

n= int(input())
array= list(map(int,input().split()))
group_count=0 
# 3 2 2 2 1  
array.sort(reverse=True)
print(array)

while len(array) >0 :
    max= array[0]
    for _ in range(max):
        array.pop(0)
    group_count+=1
        

print(group_count)

최댓값을 구해야 하니깐 배열을 내림차순 하고

공포도 크기만큼 배열에서 제외해야 하니깐 배열에 pop을 해줘서 제거

모범 답안

곱하기 혹은 더하기

각 자리가 숫자로만 이루어진 문자열 S

왼쪽에서 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사에 X 혹은 + 연산자를 넣어서

가장 큰 수 만들기

입력

• 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S 가 주어진다.

출력

• 첫째 줄에 만들어질수 있는 가장 큰 수 출력

# 입력 
# - 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S 가 주어진다.
# 출력 
# - 첫째 줄에 만들어질수 있는 가장 큰 수 출력

s= input()
result= int(s[0])

for i in range(1,len(s)):
    num = int(s[i])
    if(result<=1 or num<=1):
        result+=num
    else :
        result*=num

print(result)

첫번째 값을 저장한후 0또는 1인지 비교하면서 덧셈혹은 곱셈하기

1인경우에우 1*2 는 2 1+2는 3 이니깐 1 인경우에도 +가 더 최대값을 만든다.

문자열 뒤집기 *

0과 1로만 이루어진 문자열 s s에 있는 모든 숫자를 전부 같게 만들려고 한다.

연속된 하나이상의 숫자를 잡고 해야한다.

뒤집기를 할경우 0→1 또는 1→ 0

# 입력 : 첫째줄에 0 ,1 로만이루어진 문자열 s  s의 길이는 100만보다 작다 
# 출력 : 행동의 최소 횟수 
s=input()
count0 = 0 
count1 = 0
if s[0]=='1':
    count0+=1
else :
    count1+=1

# 두번째 원소부터 확인 
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        if s[i+1] =='1':
            count0 +=1
        else :
            count1 +=1

print(min(count0,count1))

# 000111000   0->1->0
# 111000111  1->0->1

만들수 없는 금액

n개의 동전을 이용하여 만들수 없는 양의 정수 금액중 최솟 값

나의 풀이

#입력  
# n개의 동전 각 동전의 화폐 단위 
#출력 
# 주어진 동전들로 만들수 없는 양의 정수 금액중 최솟값 

from itertools import combinations

combinations_list = []
n = int(input())
m = list(map(int, input().split()))

for i in range(1, n + 1):
    combinations_list.extend(list(combinations(m, i)))

sum_set = set()

for combination in combinations_list:
    combination_sum = sum(combination)
    sum_set.add(combination_sum)

sum_set=list(sum_set)
min_value=sum_set[0]
while min_value in sum_set:
    min_value+=1

print(min_value)

조합을 이용해서 동전을 이용해 만들수 있는 경우의수 다 만들고

집합을 통해서 중복을 제거한다.

그리고 조합 값들을 sum 을 통해서 만들수 있는 금액을 구하고

**sum_set**을 리스트로 변환한 후 출력하면, 원소들이 자동으로 오름차순으로 정렬.

while 문 돌면서 sum_set에 값이 존재하지 않다면 출력

모범 답안

1. 처음에는 금액 1을 만들수 있는지 확인하기 위해 target =1설정
2. target =1 을 만족할수 있는지 확인 있으면 target = 1+1 =2설정
3. target =2을 만족할수 있는지 확인 있으면 target =2+2 = 4설정
4. target = 4 을 만족할수 있는지 확인 있으면 target = 4+3 = 7 설정
5. target=7을 만족할수 있는가 우리는 8이 있으니깐 안됨 따라서 정답 7

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

# 1 2 4 8 
target= 1 
for x in data :
    # 만들수 없는 금액을 찾은 경우 반복 종료 
    if target<x :
        break
    target +=x 

# 만들수 없는 금액 출력 
print(target)

볼링공 고르기

두 사람이 서로 무게가 다른 볼링공을 고르려고 한다.

볼링공은 총 N 개 볼링공의 무게는 1 ~ M 까지의 자연수 형태로 존재

N이 5이고 M이 3이면 무게가 차례대로 1,3,2,3,2 이면 번호가 차례대로 1 ~5번까지 부여

1. a가 무게가 1인 공을 선택하는 경우 1 (무게) *4 (b 선택 경우의수) =4가지
2. a가 무게가 2인 공을 선택하는 경우 2(무게) * 2 (b 선택 경우의수) =2가지
3. a가 무게가 3인 공을 선택하는 경우 3(무게) *0 = 0가지

모범답안

from itertools import combinations 
# 입력 m :볼링공 개수 m :최대 무게 

n,m = map(int,input().split()) # 5 3 
data = list(map(int,input().split()))# 1 3 2 3 2 

array = [0]*11 

for x in data :
		# 각 무게에 대한 볼링공의 개수 카운트 
    array[x] +=1 
    # array[1]= 1
    # array[2]= 2
    # array[3]= 2

result =0 
for i in range(1,m+1):
    n-= array[i] # 무게가 i인 볼링공 (a가선택) 의 개수 제외 
    result +=array[i]*n # b가 선택하는 경우의 수 곱하기 

# i==1 n-=1 ->4  4*1
# i==2 n-=2 =>2  2*2
# i==3 n-=2 =>0  2*0


print(result ) #8

무지의 먹방 라이브

bookmark

회전판에 먹어야할 N개의 음식

1. 1번부터 음식 먹기 시작하며 ,회전판은 번호가 증가하는 순서대로 음식을 자기 앞으로 둔다.
2. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 앞으로 온다
3. 음식 하나를 1 초 동안 섭취후 남은 음식은 그대로 두고 , 다음 음식을 섭취 다음음식은 남은 음식중 다음으로 섭취해야할 가장 가까운 번호의 음식
4. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정

문제 해설

모든 음식을 우선순위 큐에 삽입한다. 마지막에는 k초 후에 먹어야할 음식의 번호를 출력해야 하므로 우선순위 큐에 삽입할때의 튜플 형태로 삽입한다.

• 1번 :8초
• 2번 : 6초
• 3번:4초

1. 첫 단계에서 가장 시간이 적게 걸리는 음식인 3번 음식을 뺀다 4초 * 남은음식 개수 (3) =12초 k=15이니깐 15-12 =3
2. 전체 남은시간이 3 초이면

(1,8) (2,6) (1,8) (2,6) 해서 4번째 순서인 2 번음식이 출력되야함

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)# 남은 음식의 개수 

    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]