[그리디-행복편] 5문제

조은지·2021년 9월 29일

1. 보물

링크 - https://www.acmicpc.net/problem/1026

코드

import sys
input = sys.stdin.readline

n = int(input())
a= list(map(int,input().split()))
b= list(map(int,input().split()))
a.sort(reverse=True)
b.sort()

answer=0

for i in range(n):
    answer+=a[i]*b[i]

print(answer)

B는 재배열하지 말랬지만,, 재배열 안했는지를 확인하는 조건은 없기 때문에 그냥 재배열 해줬다.

2. 거스름돈

링크 - https://www.acmicpc.net/problem/5585

코드

import sys

input = sys.stdin.readline

n = 1000- int(input())

#500,100,50,10,5

count = 0
money=[500,100,50,10,5,1]
for m in money:
    count += n//m
    n%=m

print(count)

행복합니다.

3. 전자레인지

링크 - https://www.acmicpc.net/problem/10162

코드

n = int(input())

button = [300,60,10]
result = []
for b in button:
    result.append(n//b)
    n%=b

if n!=0:
    print(-1)
else:
    for r in result:
        print(r,end=" ")

거스름돈이랑 똑같은 문제

4. 모험가 길드

출처 - 이것이 코딩테스트다.

문제 설명

N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.
모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.

모험가의 수와 각 모험가의 공포도가 입력으로 들어오면
최대 몇 개의 모험가 그룹을 만들 수 있는지 출력한다.

코드

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

result = 0	# 총 그룹의 수
count = 0	# 현재 그룹에 포함된 모험가의 수

for i in data:
    count += 1		# 현재 그룹에 해당 모험가를 포함시키기
    
    if count >= i:	# 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
        result += 1	# 총 그룹의 수 증가
        count = 0	# 현재 그룹에 포함된 모험가의 수 초기화

print(result)

5. 곱하기 혹은 더하기

코드

data= input()
idata=[]
#리스트로 바꾸기
for i in range(len(data)):
    idata.append(int(data[i]))
    
dp=[0]*(len(idata))

dp[0]=idata[0]
for i in range(1,len(idata)):
    dp[i]=max(dp[i-1]+idata[i],dp[i-1]*idata[i])
 
print(dp[-1])

답지코드

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)