02. 그리디

문제 1. 1이 될 때까지

입력 조건

첫 번째 줄에 N(1<=N<= 100,000)과 K(2<=K<=100,000)가 공백을 기준으로 하여 각각 자연수로 주어진다

출력 조건

첫 번째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다
1번. N에서 1을 뺍니다
2번. N을 K로 나눕니다

 

---

N, K = map(int, input().split())    #input: N, K
cnt = 0     #수행 횟수 값 초기화

while(N!=1):    #N이 1일 경우 종료 (while)
  if (N % K == 0):  #아닐 경우 N-1, count + 1
    N = N // K
    cnt += 1
  else:     #N%K==0이면 N//K, count + 1
    N -= 1
    cnt +=1
    
print(cnt)

---

문제 2. 곱하기 혹은 더하기

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

입력 조건

첫 번째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어진다 (1 <= S의 길이 <= 20)

출력 조건

첫 번째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다1번. N에서 1을 뺍니다

 

---

#1. 문자열 S를 입력 받는다
#2. 문자열 S의 값을 쪼개서 리스트에 넣는다
#3. 0이나 1일 경우 더하기 연산을, 그 외에는 곱 연산을 수행한다
#4. 결과를 출력한다

S = list(input()) #1, 2
S = list(map(int, S))
result = S[0]

for i in range(1, len(S)):
  if result == 0 | 1 or S[i] == 0 | 1:
    result += S[i]
  else:
    result *= S[i]
    
print(result)

---

문제 3. 모험가 길드

각 모험가 별 측정된 공포도 X를 바탕으로, 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다. 모든 모험가를 특정한 그룹에 넣을 필요는 없다.

입력 조건

첫 번째 줄에 모험가의 수 N이 주어진다 ( 1 <= N <= 10,000)
두 번째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분한다

출력 조건

여행을 떠날 수 있는 그룹 수의 최댓값을 출력한다

 

---

# 1.모험가 수, 공포도 입력
N = int(input())
group = list(map(int, input().split()))
group.sort()

result = 0
current = 1

# 2."현재 그룹에 포함된 모험가의 수 >= 현재 확인하고 있는 공포도"일 경우 그룹 생성
for i in group:
  if current >= i: 
    result += 1
    current = 1
  else:
    current += 1

print(result)

* 문제 해결 아이디어 참고