[Algo Rhythm🕺💃]BOJ 2309 - 일곱 난쟁이

문제 분석

문제에서 주어지는 아홉 난쟁이들의 키의 합은 일곱 난쟁이들의 키의 합인 100보다 크다. 따라서 이 문제는 $i$번째 난쟁이와 $j$번째 난쟁이 $(1 \le i, j \le n)$의 합이 초과값과 일치하는 $(i, j)$쌍을 찾는 문제로 이해할 수 있다.

 

문제 풀이

아홉 난쟁이의 키를 배열에 저장한 뒤, 이를 오름차순으로 정렬한다. 왜냐하면 일곱 난쟁이의 키를 출력할 때 오름차순으로 출력해야 하기 때문이다.

다음으로 이중 반복문을 통해 $(i, j)$쌍을 찾는다. 만약 찾았다면 $i$번째 난쟁이와 $j$번째 난쟁이를 제외한 모든 난쟁이들의 키를 차례대로 출력한 뒤 프로그램을 종료한다.

 

복잡도 분석

난쟁이 $n$명의 키가 입력으로 주어질 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

• 시간 복잡도 : $O(n^2)$
  • $i$번째 난쟁이와 $j$번째 난쟁이의 키의 합이 초과값과 일치하는 $(i, j)$쌍을 찾기 위해 $O(n^2)$ 가 소요됨.
  • 난쟁이들의 키가 저장된 배열을 sort하기 위해 $O(nlogn)$이 소요됨.

 

• 공간 복잡도 : $O(n)$
  • 난쟁이들의 키를 저장하기 위한 배열에 $O(n)$이 소요됨.

 

코드

 

문제 출처

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이