[구름 Level] 구슬 주머니

https://level.goorm.io/exam/49102/%EA%B5%AC%EC%8A%AC-%EC%A3%BC%EB%A8%B8%EB%8B%88/quiz/1

구름LEVEL

---

-풀이-

내용은, i번째 구슬을 뺀 나머지 값의 합을 2로 나눈뒤, 2로 나눈 구슬이 있냐 없냐에 따라 결과를 정한다.

한 구슬을 뺀 나머지 구슬들의 합이 10이라고 한다면, 한개는 5, 나머지의 합이 5가 되어야 좋은 주머니가 된다. 따라서 나머지 구슬 중 , 5를 가진 구슬이 있다면, 좋은 주머니가 된다.

 

이때, i번째 구슬을 뺀 나머지 값의 합이 홀수라면, 어떤 경우라도 좋은 주머니가 될 수 없다.

예를들어 i번째 구슬을 뺀 나머지 값의 합이 11이라고 한다면, 구슬하나를 A, 나머지 구슬의 합을 B라 할때, A+B=11, A=B가 되어야 하는데 , A+B의 값이 홀수라면 성립되지 않기때문이다.

따라서 우리는 짝수인 경우만 고려해주면 된다.

 

마지막으로 현재 뺀값과 중간값이 같다면, 현재 뺀 값이 2개 이상이여야만 답이되므로, 그것도 고려해주어 코드를 짜야한다.

 

-코드-

 

#include <iostream>
#include<map>
#include<vector>
using namespace std;
vector<long long> v;
vector<int> answer;
map<long long,int> m;
int n;

int main() {
	cin>>n;
	v.resize(n);
	long long sum=0;
	for(int i=0;i<n;i++){
		cin>>v[i];
		m[v[i]]++;
		sum+=v[i];
	}
	for(int i=0;i<n;i++){
		sum-=v[i];
		if(sum%2==0){
			long long mid=sum/2;
			if(m[mid]>=1){
				if(mid==v[i]){
					if(m[mid]>=2){
						answer.push_back(i+1);
					}
				}
				else{
					answer.push_back(i+1);
				}
			}
		}
		sum+=v[i];
	}
	cout<<answer.size()<<"\n";
	for(int i=0;i<answer.size();i++){
		cout<<answer[i]<<" ";
	}
	return 0;
}