[BOJ/백준] 2309 일곱 난쟁이

● [문제번호 2309] 일곱 난쟁이

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

2309번: 일곱 난쟁이

 

● 알아야 할 것

: 브루트 포스 (Brute Force)

: vector 자료구조와 메소드

 

● 풀이 과정

: 9명 중 7명을 선택 == 9명 중 2명을 제외

따라서 제외할 2명의 조합을 모두 탐색하면서 조건에 맞는 지 확인한다.

 

● 주의 할 것

: NULL

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// height : 입력된 난쟁이 키
vector<int> height;
// total : 9명 전체 난쟁이 키
// index1, index2 : 9명 중 제외될 난쟁이 2명
int total, index1, index2;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    height.assign(9, 0);
    
    // 입력 + 9명 전체 난쟁이 키 저장
    for(int i = 0; i < 9; i++)
    {
        cin >> height[i];
        total += height[i];
    }
    
    // 정렬
    sort(height.begin(), height.end());
    
    // 제외할 난쟁이 2명의 조합을 모두 확인
    for(int a = 0; a < 9 - 1; a++)
    {
        for(int b = a + 1; b < 9; b++)
        {
            // 난쟁이 7명의 키 총합이 100 인 경우
            if(total - height[a] - height[b] == 100)
            {
                index1 = a;
                index2 = b;
                break;
            }
        }
        
        // 난쟁이 7명의 키 총합이 100 인 경우
        if(index1 != index2)
            break;
    }
    
    // 난쟁이 7명의 키 출력
    for(int i = 0; i < 9; i++)
    {
        if(i == index1 || i == index2)
            continue;
        else
            cout << height[i] << " ";
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [500 - 브루트 포스] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	2309	일곱 난쟁이	https://pirateturtle.tistory.com/228
2	3085	사탕 게임	https://pirateturtle.tistory.com/229
3	1476	날짜 계산	https://pirateturtle.tistory.com/230
4	1107	리모컨	https://pirateturtle.tistory.com/231
5	14500	테트로미노	https://pirateturtle.tistory.com/232
6	6064	카잉 달력	https://pirateturtle.tistory.com/233
7	1748	수 이어 쓰기 1	https://pirateturtle.tistory.com/234
8	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/235