[백준/c++] 2309 - 일곱 난쟁이

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

2309번: 일곱 난쟁이

---

1) 풀이

이 문제를 알고리즘 공부 막 시작했을 때 한 번 마주한 적이 있다.

그때는 아무 것도 모르니까 어떻게 풀어야 할지 감도 안 오고...!

이리저리 헤매다가 결국 몇달 공부하고 나서야 맞힐 수 있었던 문제인데

오랜만에 다시 푸니까 약간의 실수(밑에 적어놓음) 빼고는 스무스하게 풀린다! 꽤 기쁜일...

티는 안 나지만 그래도 나도 실력이 늘고 있구나 싶구😊

 

아무튼, 난쟁이 7명 키의 총합은 100인 것을 이용해 문제를 풀었다.

 

1) input으로 난쟁이들의 키가 주어질 때, 0으로 초기화된 sum 변수에 그 input 값들을 다 더한다.

2) sum에서 100을 뺀 값을 구한다(그 값을 변수 find라고 하자)

3) 이중 for문을 만들고 인덱스를 늘려가며 차례대로 두개씩 더해본다

4) 두개 더한 값이 find와 값이 같으면 그 두개를 0으로 초기화하고

(나는 일반 int 배열을 만들었기 때문. 자료형에 따라서 처리해주면 된다)

for문을 break 시켜준다.

 

그런데!!!!!! 바로 위의 4) 에서 내가 약간 실수했던 대목이 있었다.

break 를 해줘서 반복문을 잘 빠져나온듯❗ 보였으나,

잘 살펴보면 이중 for문을 사용했기에,,,이 for문 두개를 모두 빠져나오려면

'내부 for문이 종료되었습니다.'를 알리는 별도의 변수를 두어 처리해주어야

외부 for문도 종료될 수 있다!!!! 이점 유의!!!!

그렇지 않으면 내부 for문을 break 하고도 외부 for문이 빠져나오지 못해서

조건에 맞는 다른 쌍도 찾아주게 된다😂문제에서 요구하는 것은 하나의 정답

 

이 모든 것을 처리해주고, 0으로 초기화한 값 빼고 배열의 모든 값을 출력해주면 된다!

자세한 건 소스코드를 참조하길 바란다

2) 최종 소스코드

#include <bits/stdc++.h>
using namespace std;
int arr[9]; //난쟁이 키 저장할 배열
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int sum = 0; //난쟁이 키 모두 더할 변수
	for (int i = 0; i < 9; i++) {
		cin >> arr[i];
		sum += arr[i]; //더해준다
	}
	int find = sum - 100; //모두 더한 것에서 100을 뺀 값. 
	//7명 키를 합한게 100이라고 했으므로, 결국 어떤 두값을 더했을때 sum에서 100뺀값과 똑같으면 진짜 난쟁이 아닌 것
	bool end = false; //외부 for문을 나오게 할 변수
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (i == j) continue; //같은 난쟁이의 키를 더할 순 없으므로
			if (arr[i] + arr[j] == find) {
				arr[i] = 0;
				arr[j] = 0;
				end = true; //외부 for문을 종료하겠다는 의미
				break;
			}
		}
		if (end == true) break; //true 되면 종료
	}
	sort(arr, arr + 9);
	for (int i = 0; i < 9; i++) {
		if (arr[i] == 0) continue; //0인값은 진짜 난쟁이 아닌 난쟁이들
		cout << arr[i] << '\n';
	}
}

3) 참고자료