2309: 일곱 난쟁이

2309번: 일곱 난쟁이 (acmicpc.net)

2309번: 일곱 난쟁이

 

일곱 난쟁이 

스페셜 저지

시간 제한             메모리 제한                 제출                            정답                    맞힌 사람                정답 비율

2 초

128 MB

101905

41716

30177

42.060%

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

예제 입력 1 복사

20
7
23
19
10
15
25
8
13

예제 출력 1 복사

7
8
10
13
19
20
23

막 적음

 

 

탈락된 내 코드

#include <bits/stdc++.h>

using namespace std;

int n=9, r=7;
vector<int> heights;
void combi(int start, vector<int> &v){
	//3. 다 뽑았을 경우에 합이 100이 된다면 오름차순 출력 
	if(v.size()==r){  
		int sum;
		for(int vv:v) sum += vv;
		if(sum==100){ 
			for(int vv:v) cout << vv << "\n";			
		}
	}
	for(int i=start+1;i<n;i++){
		v.push_back(heights[i]);
		combi(i,v);
		v.pop_back();
	}
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//1. 문제 입력
	int h;
	for(int i=0;i<9;i++){
		cin >> h;
		heights.push_back(h);
	}  
	sort(heights.begin(), heights.end());
	//2. 조합 
	vector<int> v;
	combi(-1,v);
	
	return 0;
}

조합 코드 그대로 사용했는데 틀렸다고 나와서 당황스러웠다.

 

정답코드

• 9C7 = 9C2와 같다.

즉, 모든 난쟁이들의 키의 합에서 두 가짜 난쟁이의 키를 빼면 100이 나온다.

 

r이 2이므로 재귀보다 for문을 사용하자.

• break를 사용하여 필요없는 반복을 줄이자.(가지치기)

 

여기까지 보고 코드를 작성했다.

#include <bits/stdc++.h>

using namespace std;

int n=9;
vector<int> heights;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//1. 문제 입력
	int h;
	for(int i=0;i<n;i++){
		cin >> h;
		heights.push_back(h);
	}  
	//2. 모든 난쟁이들의 키의 합 구하기  
	int sum=0; 
	for(int h : heights) sum += h; 
	//3. 조합 
	pair<int,int> fake; //가짜 난쟁이 2명 
	vector<int> v;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(sum - (heights[i]+heights[j]) == 100){ //가짜 난쟁이 2명 찾으면 
				fake={heights[i], heights[j]};
				break; //가지치기 
			}
		}
	}
	//3. 오름차순으로 정렬하여 출력 
	sort(heights.begin(), heights.end());
	for(int h:heights){
		if(h!=fake.first && h!=fake.second){ //가짜 난쟁이를 제외하고 출력 
			cout << h << "\n";
		}
	}
	
	return 0;
}

통과

선생님 코드

조합과 순열로 푸는 2가지 방법이 있다고 하셨다.

순열은 조합을 포함하는 개념이므로 ex) (1,2), (2,1) vs (1,2) r이 작을때는 둘 다 사용이 가능하다.

조합으로 푸는 방법

#include <bits/stdc++.h>

using namespace std;

int a[9], sum;
vector<int> v; 
pair<int,int> ret;
void solve(){
	for(int i=0;i<9;i++){
		for(int j=0;j<i;j++){
			if(sum-a[i]-a[j]==100){
				ret = {i,j}; //인덱스 사용 
				return; //가지치기 
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//1. 문제 입력
	for(int i=0;i<9;i++){
		cin >> a[i]; sum+= a[i]; //입력받으면서 합도 함께 구함 
	}
	//2. 조합을 이용한 가짜 난쟁이 찾기 
	solve();
	//3. 진짜 난쟁이만 벡터 v에 추가 
	for(int i=0;i<9;i++){
		if(ret.first==i||ret.second == i) continue;
		v.push_back(a[i]);
	}
	//4. 오름차순으로 정렬 
	sort(v.begin(), v.end());
	for(int i:v) cout << i << " ";
	
	return 0;
}

포인트

• 나쁜 난쟁이를 찾을때 값을 가져오는게 아닌 인덱스를 가져왔다.(배열 원소 접근시에 시간이 걸리기때문)
• return;으로 가지치기
• 배열 값을 입력받으면서 합도 함께 구했다(반복문 여러번 방지)
• 입력시에는 벡터보다는 배열이 나은거같다.(값 접근, 수정 쉬움)

 

유의할 점

• pop_back()시에는 push_back(값)과 다르게 인자가 없다.
• 문제를 꼼꼼히 보자(오름차순 출력 조건)
• 변수 이름을 겹치지않게, real같은 이름은 bits/stdc++.h에서는 사용 불가능하다.
• 옳은 로직도 중요하지만 같은 길을 빠르게 가는 방법도 중요하다.
  • 조합을 사용하는 문제는 nCr = nCn-r 을 생각하자.

 

sort()

오름차순 정렬

sort(시작주소, 시작주소+총 원소개수)

ex ) a[10]일때 sort(a, a+10);

sort(시작iterator, 끝 iterator)

ex ) sort(v.begin(), v.end());

세번째 인자-비교 기준 결정 가능

ex) sort(v.begin(), v.end(), less<int>) 

 

https://blockdmask.tistory.com/178

[C++] sort algorithm 정리 및 예시

 

<bits.stdc++.h> 사용 불가 변수명

키워드는 사용불가능하다.

real, x0, y0, yn, j0, j1, jn, visit, time, prev, next  등등

 

 

bits/stdc++.h의 헤더파일 : https://miniolife.tistory.com/11

Visual Studio에서 <bits/stdc++.h> 사용하기

 

순열로 푸는 방법

9명 중 7명의 키의 합은 100이다.

문제에서 "일곱 난쟁이를 찾을 수 없는 경우는 없다" 라고 언급하였으므로

9개를 순열로 하여 앞에 7개만 slice한다.

처음부터 차례대로 원소들의 합을 조사한 후 100이면 break한다.

((1,2)와 (2,1) 처럼 겹치더라도 합은 3으로 같기때문에 (1,2)에서 break가 된다.)

 

#include <bits/stdc++.h>
using namespace std;

int a[9];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//1. 입력받기  
	for(int i=0;i<9;i++) {
		cin >> a[i];		
	}
	//2. 오름차순으로 정렬 
	sort(a,a+9);
	//3. 합이 100이 되는 난쟁이 찾기 
	do{
		int sum=0;
		for(int i=0;i<7;i++) sum +=a[i];
		if(sum==100) break;
	}while(next_permutation(a,a+9));
	//4.진짜 난쟁이 출력 
	for(int i=0;i<7;i++) cout << a[i] << "\n";
	return 0;
}

 

유의할 점

• 지역변수 초기화 꼭 하기! 자주쓰는 변수들은 전역변수로!(전역변수는 자동으로 값이 초기화가 되기때문이다.)
• next_permutation 사용시엔 미리 오름차순으로 정렬된 상태여야한다.

 

피드백에 근거한 최종 코드(조합 사용)

#include <bits/stdc++.h>

using namespace std;

int n=9, sum;
int a[9]; //입력배열 
vector<int> v; //진짜 난쟁이들 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//1. 문제 입력	
	for(int i=0;i<n;i++){
		cin >> a[i]; //입력 받을때는 벡터보단 배열이 편하다. 
		sum+=a[i]; //한번에 합까지 구하기 
	}  

	//2. 조합 
	pair<int,int> fake; //가짜 난쟁이 2명 
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(sum - (a[i]+a[j]) == 100){ //가짜 난쟁이 2명 찾으면 
				fake={i,j}; //인덱스 저장 
				break; //가지치기 
			}
		}
	}
	//3. 진짜 난쟁이 모음
	for(int i=0;i<9;i++){
		if(i==fake.first || i==fake.second) continue; //가짜 난쟁이이면 패스 
		v.push_back(a[i]);
	} 
	//3. 오름차순으로 정렬하여 출력 
	sort(v.begin(), v.end());
	for(int vv:v) cout << vv << "\n";
	
	return 0;
}

 

재귀 코드

#include <bits/stdc++.h>
using namespace std;
int n=9, r=7;
int a[10];

void solve(){
	int sum = 0;
	for(int i=0;i<r;i++) sum += a[i];
	if(sum==100){
		sort(a, a+7);
		for(int i=0;i<7;i++) cout << a[i] << "\n";
		exit(0);
	}
}

void makePermutation(int n, int r, int depth){
	if(depth==r){
		solve();
		return;
	}
	for(int i=depth; i<n; i++){
		swap(a[i], a[depth]);
		makePermutation(n, r, depth+1);
		swap(a[i], a[depth]);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	makePermutation(n, r, 0);
}