개요

[링크]백준 2309번: 일곱 난쟁이

간단히 요약하면 9가지 숫자 값을 입력받고.
그 중 합이 100이 되는 7가지 수를 올림으로 정렬해
출력하는 것이다.

접근 방식

일단 7 가지 수를 가지고 뭔가를 하기보단
나머지 두 가지 수를 가지고 푸는게
더 효율적이란 것까진 생각을 했다.

하지만 두 가지 수를 제외한 값의 합이
100임을 확인하고, 나머지 값들을 정렬하는 과정에서
헤매다가 결국 O(n^3)의 시간복잡도로
구현하게 되었다.

다행히 n의 값이 9밖에 안되어서 충분히 해결되었지만
9가지가 아니라 만약 천 이상의 값이였다면
1초는 넘기니 다른 방식을 찾아야 했다.

접근 코드

#include<iostream>							//3
#include<vector>
#include<algorithm>
using namespace std;

int arr[10] = {0,};	//초기화
vector<int> ans;

void input() {
	for(int i=0;i<9;i++)
		cin >> arr[i];
}

void solution() {
	int sum = 0;
	for (int i = 0; i < 9; i++) {			//첫번째 난쟁이 정하기
		for (int j = i+1; j < 9; j++) {		//두번째 난쟁이 정하기
			for (int k = 0; k < 9; k++) {	
				if (k != i && k != j) {		
					sum += arr[k];			//두 값 제외한 값 다 더해주기
					ans.push_back(arr[k]);	//답 벡터에 push_back
				}

			}
			if (sum == 100) {				//다른 두 값 합이 100이면
				sort(ans.begin(), ans.end());//algorithm헤더의 sort함수로 정렬
				for (int elem : ans)
					cout << elem << '\n';		//ans벡터의 원소 출력
				return;
			}
			else {
				ans.clear();				//100이 아니면 ans벡터 초기화
				sum = 0;					//sum값도 초기화
			}
		}
	}
}

int main() {
	input();
	solution();
}

다른 방식

1. 처음에 9 가지 값을 다 더한 후
   100을 뺀 나머지 값을 저장.

2. 합이 나머지 값이 나오는 두 값을 찾는다.

3. 찾은 후 그 두 값을 0으로 바꿔준 후
   배열을 정렬한다.

4. 배열 값이 0이 아닌 것들을 차례대로 출력해준다.

이 방식이면 i와 j만 사용을 하여 O(n^2)의
시간복잡도이므로 더 효율적이다.

다른 방식의 코드

void solution()부분만 변경되므로 solution함수만 올림.

void solution() {					//다른 풀이
	int sum = 0,rem=0;
	for (int i = 0; i < 9; i++)
		sum += arr[i];
	rem = sum - 100;				//다 더한값에서 100을 빼고 
									//나머지 값 저장
	for (int i = 0; i < 9; i++) {
		for (int j = i+1; j < 9; j++) {
			if (arr[i] + arr[j] == rem) {	//두개 더한값이 나머지값이 나오면 
											//나머지 값들을 다 더해야하는데
				arr[i] = 0;					//값에 0저장		
				arr[j] = 0;
				sort(arr, arr + 9);			//정렬
				for (int elem : arr) {
					if (elem != 0) {			//원소가 0이 아니면
						cout << elem << '\n';	//출력
					}
				}
				return;
			}
		}
	}

}

문 풀 후 생

값들을 다 더한 후
100에서 뺀 나머지 값을 이용하는 것도
생각을 못했고,

나머지 7 가지 값들을
다른 배열에 저장해야 겠다는 생각이 가득찬게
실패 요인인거 같다.
찾았을 때 두 값들을 0으로 변경 후
바로 정렬해서 0 아닌 값을 출력하는 방법은
계속 떠올려야할 괜찮은 스킬 같다.