Budget (c++)

과정

1. 모든 경우의 수를 구해서 가장 많이 물건을 살 수 있는 경우 고르기? → O(n!)

 

2. 벡터를 정렬해서 작은 숫자부터 확인해보기

• 정렬 알고리즘 - algorithm의 sort → O(nlogn)
• 앞에서부터 예산 확인하기 - 최악의 경우 전부 확인 → O(n)

sol

1. 정렬 알고리즘으로 d 정렬하기 → O(nlogn)

 

2. for문으로 budget에서 작은 가격부터 감산하고, 할 수 있으면 answer++

 

3. 감산한 값이 0보다 작으면 더 이상 예산을 사용할 수 없으므로 값 return 

고민

• 처음에는 budget에서 d[i]를 뺄 생각을 못해서 sum이라는 새로운 변수를 만들어서 사용했다.
• int 변수 1개라서 4 bytes의 메모리라도 어떻게 보면 낭비!
• 메모리를 줄일 수 있는 방법이 있는지 풀기 전에 한 번 생각해보는 습관을 들여보자!

 

shin0112/programmers_cpp: programmers' coding test solutions (github.com)

출처 : 프로그래머스 코딩 테스트 연습 - Budget
https://school.programmers.co.kr/learn/courses/30/lessons/12982