[이코테-그리디]곱하기 혹은 더하기, 모험가 길드

iamjinseo·2022년 8월 3일

문제풀이-Python

목록 보기

29/134

곱하기 혹은 더하기

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 ‘×’ 혹은 ‘+’ 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 ×를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2) × 9) × 8) × 4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

입출력

02984 => 576
567 => 210

해설

두 수 중에서 하나라도 1 이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하기

코드

# 숫자 문자열 입력
data = input()

# 결과 (프로그램 시작 시 결과는 맨 앞 수)
# 숫자 앞에서부터 연산해온 결과라고 볼 수 있음
result = int(data[0])

for i in range(1, len(data)):
    num = int(data[i])
    if num <=1 or result<=1 : #현재 수가 1 이하거나 앞 수가 1 이하일 때
        result += num
    else :
        result *= num

print(result)

내가 한 생각

0이면 무조건 더하기고 나머지를 곱하기라 생각함
알고보니 1이 나와도 더하기를 해야 유리함을 알아냄

모험가 길드

한 마을에 모험가가 N명 있습니다. 모험가 길드에서는 N명의 모험가를 대상으로 ‘공포도’를 측정했는데, ‘공포도’가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.
• 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.
• 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요

입출력

<입력>
5
2 3 1 2 2
<출력>
=> 2

해설

공포도를 오름차순 정렬하고
공포도를 순회하면서 일단 현재 공포도를 갖고있는 사람을 그룹에 넣고
그룹 인원수가 현재 공포도 이상이면(내가 안쫄아도 되면)그룹 구성을 끝내고 그룹 수를 +1, 그리고 그룹 인원 초기화

코드

#인원수 입력
n = int(input())

# 인원수만큼의 공포도 입력
data = list(map(int, input().split()))
# 공포도 오름차순 정렬
data.sort()

count =0 # 그룹 내 인원수 
result = 0 # 최종 그룹 수

# 공포도 순회
for i in range(len(data)):
    count +=1   # 현재 공포도의 사람을 그룹에 넣기
    if count >= i : # 그룹 인원수가 현재 공포도 이상이면
        result +=1   # 그룹 하나를 구성한다
        count =0 # 그룹의 인원수를 초기화한다(다음 그룹 구성으로 넘어간다)

print(result)