bright

n = int(input())
data= [0]*3001

# 5, 3, 2 로 나누거나 1 빼기.. 
# 연산한 것이 무엇이 가장 작은지 판별
# +1 은 계산 횟수를 더해주기 위한 것. 
# bottom up 방식이므로.. i//k < i 를 만족해서 다음처럼 표현 가능.. 

for i in range(2,n+1):
  d[i] = d[i-1]+1

  if i %2 == 0:
    d[i] = min(d[i], d[i//2]+1)
  if i %3 == 0:
    d[i] = min(d[i], d[i//3]+1)
  if i %5 == 0:
    d[i] = min(d[i], d[i//5]+1)

print(d[n])

1. 재귀 함수   // 시간 복잡도 : O(2^n)

def fivo(x):
  if x == 1 or x == 2 :
    return 1
    
  return fivo(x-1)+ fivo(x-2)

2. Top-down 방식 , Memoization 기법 사용 ( Cashing )   // 시간 복잡도 : O(N) 

# 계산된 피보나치 결과를 저장하는 리스트 선언 
result = [0] * 100 

def fivo(x):
  if x == 1 or x == 2 :
    return 1 
  
  if result[x] != 0 :
    return result[x]

  d[x]= fivo(x-1)+fivo(x-2)
  return d[x]

3. Bottom-up 방식 

# 계산된 피보나치 결과를 저장하는 리스트 선언 
result = [0] * 100 

result[1]=result[2]=1
n = 99 

for i in range(3,n+1):
  d[i] = d[i-1]+d[i-2]

1. 순차 탐색 -> 시간오류 날 것.. 

n,m = map(int, input().split())
data = list(map(int, input().split()))

data = sorted(data,reverse=True)

l = data[0]
sum = 0 
while sum < m :
  sum = 0 
  for i in data:
    if l-i <= 0 : 
      pass
    else :
      sum += l-i 

print(sum)

2. 파라메트릭 서치 -> 이진탐색 

n,m = map(int, input().split())
data = list(map(int, input().split()))

start = 0 
end = max(data)

result = 0 
while start<= end:
  sum = 0 
  mid = (start + end) //2 

  for i in data:
    if i > mid :
      sum += (i-mid)
    
  if sum < m : 
    end = mid -1 
  else : 
    result = mid
    start = mid +1 

print (result)

n = int(input())  # 내가 가진 것 
ndata = list(map(int,input().split()))
m = int(input())  # 상대의 요청 
mdata = list(map(int,input().split()))

ndata.sort()

def bin_sort(arr,start,end,target):
  if start> end:
    return None 
  
  mid = (start + end) // 2 
  
  if target > arr[mid]:
    return bin_sort(arr,mid+1,end,target)
  elif target == arr[mid]:
    return True
  else : 
    return bin_sort(arr,start,mid-1,target)

for i in mdata:
  result = bin_sort(ndata,0,n-1,i)

  if result : 
    print('yes', end=' ')
  else : 
    print('no', end=' ')

https://programmers.co.kr/learn/courses/30/lessons/42889

# 2019 카카오 신입 공채 1차 

# 3 개 시간 초과

def solution(N, stages):
    stages.sort()
    result = [ [i,0] for i in range(1,N+1)]
    
    def cnt(stages, k):
        sum = 0 
        for i in stages:
            if i >= k:
                sum += 1
        return sum 
       
    for i in range(N):
        if cnt(stages,i+1) != 0 :
            result[i][1] = stages.count(i+1) / cnt(stages,i+1)
        else :
            result[i][1] = 0 

    result = sorted( result, key= lambda x: x[1], reverse=True)
    
    answer = []
    for i in result:
        answer.append(i[0])
    return answer

채점 결과

정확성: 88.9

합계: 88.9 / 100.0