[알고리즘] 그리디 알고리즘

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법

그것이 결국 최적의 해가 되는지 정당성 분석이 중요함

 

# 문제 1

 

# 해결

n을 k로 나눠 n을 작게 만드는게 포인트. 그래야 연산 시간이 적게 걸림. 시간복잡도가 logn 정도로 낮아진다는 점.

import sys
input = sys.stdin.readline

n,k=map(int,input().split())
cnt=0
while True:
    target=(n//k)*k   #target : k의 배수 중 n과 가장 가까운 수 (n보다 작은 수 중, n과 가까운수)
    cnt+=n-target     #n이 target이 될때까지 1을 빼주는 과정을 횟수에 카운트
    n=target          # 이제 n은 k의 배수가 됨
    n=n//k 
    cnt+=1
    if n<k:           #나누는수 k보다 작아지면 탈출
        break
cnt+=(n-1)            #n이 1이 될때까지 n-1번 빼줘야함. 횟수 카운트
print(cnt)

 

#문제 2

 

 

#해결

import sys
input = sys.stdin.readline

s=input().rstrip()
res=0
nums=list(map(int,s))

for n in nums:
    if n<=1 or res<=1:   #두수가 0,1 일때는 a+b > a*b 로 덧셈이 더 크다.
        res+=n
    else:
        res*=n
print(res)

 

#문제

 

#해결

import sys
input = sys.stdin.readline

n=int(input().rstrip())
arr=list(map(int,input().split()))
group=0
arr.sort()       #오름차순 정렬, 공포도 작은것부터 확인함
i=0

while True:
    if i>=len(arr)-1:
        break
    i=i+arr[i]
    group+=1
print(group)

출처- 이것이 코딩테스트다 with 파이썬