[백 준/구현] 2309: 일곱 난쟁이

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

2309번: 일곱 난쟁이

for문

arr = []
for i in range(9):
	n = int(input())
	arr.append(n)

one = 0
two = 0

SUM = sum(arr) # 총합
for i in range(9):
	for j in range(i+1, 9):
		if SUM - (arr[i] + arr[j]) == 100: 
			one, two = arr[i], arr[j]
			break # 반복문 탈출
arr.remove(one)
arr.remove(two)
for i in sorted(arr):
	print(i)

간단하게 생각하면 결국 9명 중 7명을 뽑아 그 합이 100이면 해당 원소값들을 오름차순으로 출력해주면 된다. 그런데 단순 반복문을 7개 중첩하는 것은 매우 비효율적이므로 반대로 생각을 해보자. 9명 중 2명을 뽑아 그 2명 키의 합을 전체 키에서 뺀 값이 100이라면 반복문을 7회->2회만 중첩하여 실행시키면 된다. 

조합, combination

from itertools import combinations

arr = []
for i in range(9):
	n = int(input())
	arr.append(n)

for i in combinations(arr, 7):
	if sum(i) == 100:
		for j in sorted(i):
			print(j)
		break

이렇게 조합 라이브러리를 사용해서 풀어도된다.

itertools 사용하기

파이썬에 내장된 itertools패키지의 combinations모듈과 permutations모듈을 통해 쉽게 순열과 조합을 구할 수 있다. 이때, 만들어진 순열과 조합은 튜플의 형태로 리스트에 담겨서 반환된다. -> [(0, 1, 2), (0,1,3) ...(3,4,5)]

조합

from itertools import combinations

arr = [0, 1, 2, 3, 4, 5]

print(list(combinations(arr, 3)))

순열

from itertools import permutations

arr = [0, 1, 2, 3, 4, 5]

print(list(permutations(arr, 3)))

추가 학습

[20, 7, 23 , 19, 10, 15, 25, 8, 13] 이라는 배열 중에서 하나의 index를 고정하고 그 다음 index와 하나씩 더하는 로직은 다음과 같다. 

height = [20, 7, 23, 19, 10, 15, 8, 13]
for i in range(len(height)):
    for j in range(i+1, len(height))

또한 반복문을 사용할 때 break 걸어주는거 잊지 않고 고려하기! 

C++ 코드

// ConsoleApplication2.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int arr[9]; // 9개의 정수를 저장할 배열
	int sum = 0; // 모든 정수의 합을 저장할 변수
	for (int i = 0; i < 9; i++) {
		cin >> arr[i]; // 사용자로부터 9개 정수를 입력받아 arr에 저장
		sum += arr[i]; // 각 입력값을 더해 전체 합 계산
	}
	sort(arr, arr + 9); // arr을 오름차순으로 정렬
	// 합이 100이 되는 조합 찾기
	for (int i = 0; i < 8; i++) {
		for (int j = 1; j < 9; j++) {
			if (sum - arr[i] - arr[j] == 100) {
				// 조합 출력
				for (int k = 0; k < 9; k++) {
					// 두 정수 를 제외한다. || == OR
					if (k == i || k == j) continue;
					cout << arr[k] << '\n';
				}
				return 0; // 프로그램 종료
			}
		}
	}
	return 0;

}