ALiNew ALiNew

일곱 난쟁이

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

  Algo Rhythm🕺💃/BOJ 2021. 6. 22. 20:02

  문제 분석 문제에서 주어지는 아홉 난쟁이들의 키의 합은 일곱 난쟁이들의 키의 합인 100보다 크다. 따라서 이 문제는 $i$번째 난쟁이와 $j$번째 난쟁이 $(1 \le i, j \le n)$의 합이 초과값과 일치하는 $(i, j)$쌍을 찾는 문제로 이해할 수 있다. 문제 풀이 아홉 난쟁이의 키를 배열에 저장한 뒤, 이를 오름차순으로 정렬한다. 왜냐하면 일곱 난쟁이의 키를 출력할 때 오름차순으로 출력해야 하기 때문이다. 다음으로 이중 반복문을 통해 $(i, j)$쌍을 찾는다. 만약 찾았다면 $i$번째 난쟁이와 $j$번째 난쟁이를 제외한 모든 난쟁이들의 키를 차례대로 출력한 뒤 프로그램을 종료한다. 복잡도 분석 난쟁이 $n$명의 키가 입력으로 주어질 때, 시간 복잡도와 공간 복잡도는 다음과 같다. 시간 복..

  Read More