[これがコードテスト]2グリディ

グレースケールアルゴリズム

金をさがす

<正当性分析>

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin # 화페로 나눈 나머지 n에 대입

print(count)

<問題>1まで

# 내 풀이 -> 시간 오래걸림..
import sys
n,k=map(int,sys.stdin.readline().split())
cnt=0

while n>1:
    if n%k!=0:
        n-=1
        cnt+=1
        
    else:
        n=n//k
        cnt+=1

print(cnt)

import sys
n,k=map(int,sys.stdin.readline().split())
result=0
while True:   
    target=(n//k)*k # n이 k로 나누어 떨어지지 않을 때, k의 배수에서 n보다 작은 수를 target에 넣음 
    result+=(n-target) # 1빼주는 연산 수행 횟수를 result에 더함.
    n=target

    if n<k:
        break

    result+=1 # 
    n=n//k 

result+=(n-1)
    
print(result)

<問題>乗算または加算

私の答え

import sys
s=sys.stdin.readline()
num_list=[]
result=1


for num in s[:-1]: # 문자열을 배열로 분배.
    num_list.append(int(num))

num_list.sort() # 

if num_list[0]==0 or num_list[0]==1: # 첫 배열의 항목이 0, 1인 경우 예외 처리 
    result=num_list[0]+num_list[1]
    num_list=num_list[2:]

for num in num_list:
    result*=num
print(result)

コーディングテストの回答

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)

<問題>冒険者組合:問題の説明

내 풀이
import sys

cnt=0
n=int(sys.stdin.readline())
data=list(map(int,sys.stdin.readline().split()))
data.sort()



while len(data)!=0:
    max_fear=data.pop()
    if max_fear==1:
        cnt+=data.count(1)+1
        break
    else:
        data=data[0:-max_fear+1]
        cnt+=1
    print(data)


print(cnt)

출제자 풀이
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) # 총 그룹의 수 출력