[백준][C++] 2309번 일곱 난쟁이

일곱 난쟁이

문제 링크

일곱 난쟁이

분석

아홉 줄에 각각 난쟁이들의 키가 주어집니다.
이때, 키는 100을 넘지 않는 자연수이며, 모두 다른 값을 가집니다.

9명의 난쟁이 중 7명을 선택하여 키의 합이 100이 되도록 해야합니다.

전체 9명의 키 합을 $H$라고 하면, 제외되는 2명의 키 합은 $H - 100$이 됩니다.

따라서 문제는 9명 중에서 합이 $H - 100$의 결과값인 두 명을 찾는 문제로 볼 수 있습니다.

정렬 후 투 포인터를 사용하여 두 수의 합을 찾는 방식으로 해결할 수 있습니다.

풀이

#include <iostream>
#include <algorithm>

#define totalDwarfCount 9   // 전체 난쟁이의 수

int main()
{
	int totalDwarf[totalDwarfCount];
	
	// 9명 난쟁이 키의 전체 합
	int totalStature = 0;
	
	// 9명 키를 입력받고 전체 합을 구한다.
	for (int i = 0; i < totalDwarfCount; ++i)
	{
		std::cin >> totalDwarf[i];
		totalStature += totalDwarf[i];
	}

	// 오름차순 정렬
	std::sort(&totalDwarf[0], &totalDwarf[totalDwarfCount]);

	// 제외할 두 난쟁이를 가리키는 인덱스
	int frontIndex = 0;
	int BackIndex = totalDwarfCount - 1;

	// 일단 가장 앞, 가장 뒤 난쟁이를 제외했다고 가정하고 나머지 7명의 합을 만든다.
	totalStature -= totalDwarf[frontIndex];
	totalStature -= totalDwarf[BackIndex];

	while (true)
	{
		// 현재 남아 있는 7명의 합이 100보다 크다면 제외 대상을 더 큰 값으로 옮긴다.
		if (totalStature > 100)
		{
			// 기존에 제외했던 앞쪽 난쟁이를 다시 합에 포함
			totalStature += totalDwarf[frontIndex];
			
			// 제외할 앞쪽 난쟁이 인덱스를 한 칸 이동
			++frontIndex;
			
			// 두 인덱스가 같아질 경우 건너뜀
			if (frontIndex == BackIndex)
			{
				++frontIndex;
			}
			
			// 새로 제외할 난쟁이를 합에서 뺀다.
			totalStature -= totalDwarf[frontIndex];
		}
		// 현재 남아있는 7명의 합이 100보다 작다면 제외 대상을 더 작은 값으로 옮긴다.
		else if (totalStature < 100)
		{
			// 기존에 제외했던 앞쪽 난쟁이를 다시 합에 포함
			totalStature += totalDwarf[BackIndex];

			// 제외할 뒤쪽 난쟁이 인덱스를 한 칸 이동
			--BackIndex;
			
			// 두 인덱스가 같아질 경우 건너뜀
			if (frontIndex == BackIndex)
			{
				--BackIndex;
			}

			// 새로 제외할 난쟁이를 합에서 뺀다.
			totalStature -= totalDwarf[BackIndex];
		}
		// 현재 남아 있는 7명의 합이 정확히 100이면 정답.
		else
		{
			break;
		}
	}

	// 오름차순 출력
	for (int i = 0; i < totalDwarfCount; ++i)
	{
		if (i == frontIndex || i == BackIndex)
		{
			continue;
		}

		std::cout << totalDwarf[i] << std::endl;
	}

	return 0;
}

성능 요약

시간 복잡도는 상수 시간에 끝나기 때문에 $O(1)$입니다.

• 입력 받는 반복문 $O(9) \approx O(1)$
  • N이 $9$로 고정이므로, $1$이라고 볼 수 있습니다.
• 정렬 함수 sort $O(9 \ log \ 9) \approx O(1)$
• 투 포인터처럼 인덱스 이동 $O(9) \approx O(1)$
• $O(1) + O(1) + O(1)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

• 난쟁이 키 저장 배열 totalDwarf $O(9) \approx O(1)$
  • N이 $9$로 고정이므로, $1$이라고 볼 수 있습니다.

메모리: 2020 KB

시간: 0 ms