Dong-kipedia

BOJ 2309 일곱 난쟁이

 
  • Nov 12, 2021
  • 0 views

문제 링크

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

알고리즘 유형

브루트 포스

시간복잡도 계산

브루트 포스의 시간 복잡도는 \(O(경우의\ 수\times 각\ 경우의\ 시간\ 복잡도)\)

경우의 수

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

\({9 \choose 7} = {9 \choose 2}\)이므로 2가지 방법 존재

  1. 9명의 난쟁이 중 진짜 7명 선택
  2. 9명 난쟁이 중 가짜 2명 선택

방법의 개수는 \(O({n \choose n - 2}) = O({n \choose 2}) = O({n \choose 2}) = O(n^2)\)

1, 2번 모두 복잡도는 동일하나, 구현이 용이한 ‘2. 가짜 2명 선택’ 채택
2개 선택은 재귀 대신 반복으로 구현 가능

각 경우의 시간 복잡도

다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

1. 진짜 난쟁이 키 합계 비교

(n-2)명의 난쟁이들의 키 합계와 100 비교
시간복잡도는 \(O(n)\)

2. 가짜 난쟁이 키 합계 비교

2명의 난쟁이들의 키 합계와 전체 난쟁이 키 합계 - 100 비교
시간복잡도는 \(O(1)\)

시간복잡도가 낮은 ‘2. 가짜 난쟁이 키 합계 비교’ 채택

정렬

일곱 난쟁이의 키를 오름차순으로 출력한다.

앞의 모든 연산을 수행 후 결과 정렬 필요

시간복잡도는 \(O(nlogn)\)

총 시간복잡도

본 문제의 총 시간복잡도는 \(O(n^2\times1+nlogn) = O(n^2)\)

코드

##include <iostream>
##include <numeric>
##include <algorithm>

using namespace std;

int hgt_of_dwarf[9];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 난쟁이의 키 입력받기
    for (int dwarf = 0; dwarf < 9; ++dwarf) {
        cin >> hgt_of_dwarf[dwarf];
    }

    // 가짜 난쟁이의 키 합계 계산
    int hgt_sum_of_fakes = accumulate(hgt_of_dwarf, hgt_of_dwarf + 9, 0) - 100;

    // 가짜 난쟁이 선택하기
    int fake_hgt1, fake_hgt2;
    for (int fake1 = 0; fake1 < 8; ++fake1) {
        for(int fake2 = fake1 + 1; fake2 < 9; ++fake2) {
            if (hgt_of_dwarf[fake1] + hgt_of_dwarf[fake2] == hgt_sum_of_fakes) {
                fake_hgt1 = hgt_of_dwarf[fake1];
                fake_hgt2 = hgt_of_dwarf[fake2];
                goto end;
            }
        }
    }

end:
    // 전체 난쟁이 키 정렬
    sort (hgt_of_dwarf, hgt_of_dwarf + 9);

    // 정렬된 결과에서 가짜 난쟁이 제외
    for (int dwarf = 0; dwarf < 9; ++dwarf) {
        int hgt = hgt_of_dwarf[dwarf];
        if (hgt == fake_hgt1 || hgt == fake_hgt2) continue;
        cout << hgt << '\n';
    }
    
    return 0;
}
Search