그리디(greedy) - 볼링공 고르기

1. 문제 해결을 위한 아이디어

  ① 공 두 개를 고르는 모든 경우에서, 무게가 같은 공 두 개를 고르는 경우를 뺀다.

  ② 공 무게 리스트의 맨 처음 공부터 기준으로 해서 무게가 다른 조합을 전부 비교해서 구한다.

  ③ 무게가 가장 작은 공부터 기준으로 해서 그와 다른 무게의 공을 고르는 경우의 수를 구한다.

 

2. 소스 코드

  아이디어 ① 

 

  아이디어 ②

 

  아이디어 ③

 

3. 메모

  - 아이디어 ①, ②를 구현한 코드는 공의 개수가 늘어날수록 소요 시간이 늘어남. 
      → 주어지는 데이터의 수에 따라 시간 복잡도가 어떻게 변하는지 따져보는 것이 중요함.