[코딩테스트 26일차] BAEKJOON 2309번 : 일곱 난쟁이

[BAEKJOON 2309번 : 일곱 난쟁이]

[문제]

---

[고찰]

저는 해당 문제에 대해, 일곱 난쟁이에 포함되지 않는 키를 제외하고자 변수 n과 m을 설정하여, 무한 루프 while 문 안에서 일곱 난쟁이를 찾았습니다.

 

난쟁이들의 키를 더 한 값 sum이 100이 아니라면, 초기에 설정한 n = 8, m = 7에서 m을 1씩 빼고, m이 0보다 작을 때 n을 1씩 빼고 m을 n - 1로 설정하였습니다.

n	m	n	m	⋯	n	m
9	8	8	7		2	1
9	7	8	6
9	6	8	5
9	5	8	4
9	4	8	3
9	3	8	2
9	2	8	1
9	1

 

이런 식으로 모든 경우의 수를 확인하고자 하였습니다.

 

하지만, 이 방식 역시 너무 비효율적인 방식이라는 것을 다른 사람들의 풀이를 보고 깨달았습니다.

 

이런 식으로 무한 루프로 돌려 경우의 수를 확인할 것이 아니라, 아홉 난쟁이의 키를 모두 합친다음에 sum이 100이 되기 위한, 제외될 두 난쟁이를 중첩 for문으로 확인하면 되는 것이였습니다.

 

아이디어는 비슷하지만, 이를 구현하는 부분에 있어 제 부족한 점을 다시 한번 깨달았습니다. 이에 정리하고자 합니다.

 

아래는 제가 제출한 코드입니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	vector<int> height(9);
	
	for (int i = 0; i < 9; i++)
	{
		cin >> height[i];
	}

	sort(height.begin(), height.end());

	int n = 8;
	int m = 7;

	while (true)
	{
		int sum = 0;
		vector<int> seven;

		for (int i = 0; i < 9; i++)
		{
			if (i != n && i != m)
			{
				sum += height[i];
				seven.push_back(height[i]);
			}
		}

		if (sum == 100)
		{
			for (int i = 0; i < 7; i++)
			{
				cout << seven[i] << "\n";
			}
			break;
		}

		m--;
		if (m < 0)
		{
			n--;
			m = n - 1;
		}
	}

	return 0;
}

---

[개념]

해당 문제에서 필요한 알고리즘은 브루트포스 알고리즘으로, 모든 경우의 수를 확인하는 완전 탐색입니다.

[고찰] 부분에서 정리한 것과 같이, 아홉 난쟁이의 키를 모두 합한 뒤, 두 명의 난쟁이를 제외할 조합을 중첩 for문으로 찾습니다.

 

이때 중첩 for문 중 첫 for문은 0부터 8까지, 두 번째 for문은 i + 1부터 9까지 반복하며, sum - height[ i ] - height[ j ] == 100인 조건을 만족시킬 때 제외할 두 명의 난쟁이를 찾은 것입니다.

 

for (int i = 0; i < 8; i++)
{
    for (int j = i + 1; j < 9; j++)
    {
        if (sum - height[i] - height[j] == 100)
        {
            // i, j번째 난쟁이를 제외하고 출력
            for (int k = 0; k < 0; k ++)
            {
                if (k != i && k != j)
                    cout << height[k] << "\n";
            }
            
            return 0;
        }
    }
}

---

[정리]

문제에 대한 아이디어를 구현할 때 무한 루프 while문을 사용하게 된다면, 그것이 정말로 효율적인 구현인지를 고민해봐야겠습니다.

---

[Solution]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> height(9);
    int sum = 0;

    for (int i = 0; i < 9; i++)
    {
        cin >> height[i];
        sum += height[i];
    }

    sort(height.begin(), height.end());

    for (int i = 0; i < 8; i++)
    {
        for (int j = i + 1; j < 9; j++)
        {
            if (sum - height[i] - height[j] == 100)
            {
                for (int k = 0; k < 9; k++)
                {
                    if (k != i && k != j)
                        cout << height[k] << '\n';
                }
                return 0;
            }
        }
    }

    return 0;
}