[C++/1239] 차트

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

이 문제는 굉장히 나에게 어려운 문제였다. 오랜만에 골드 문제를 풀어서 시간이 오래걸린줄 알았는데, 푸는 방법을 세네번은 바꿔가면서 풀이한 것 같다. 처음에는 많은 조건 분기와 같은 문제인 줄 알았다. 왜냐하면 n의 개수가 1부터 8이기 때문에 어떻게 조건을 다 조합하면 풀릴 것 이라고 생각했기 때문인데,

예를 들어서 n이 1이라면? 100이기 때문에( n개의 합은 100) 당연히 중앙을 지나가는 선이 없다. 그리고 n이 2라면 50과50 또는 49 51 또는 48 52 이런식으로 나오기 때문에 50이 있다면 1개의 중앙을 지나가는 선이 있다. 근데 이런식이라면? 문제를 해결하는데 굉장히 어려움이 있다. 모든 조건을 다 쓴다면 당연히 풀리겠지만 그건 코드가 아니기 때문이다. 

이러한 과정중에 하나를 깨닫게 되는데, 50을 맞추면 하나의 선이 중앙을 지나가게 된다는 것이다. 즉, 50을 만족하는 조건이 몇개가 있냐가 관건이 되겠다.

그렇다면? 여러가지 값이 존재를하는데, 이 값들을 여러 조합으로 만들어 볼 수 있지 않을까? 즉 1,2,3,4,5 이런식으로 되어있을때 2,3,4,5,1이런식으로 바꿔도 보는 조합을 의미하는 것이고, 그리고 index 0번부터 4번까지 50이 되는 개수가 몇개인지 파악을 하는 것이다. 이러한 방식으로 전체 중앙을 지나갈 수 있는 값을 구할 수 있다.

그리고 정답을 2로 나누게 되는데 그 이유는 간단하게 [50,50]으로 되어있다고 가정하고 설명하겠다.

50은 바로 50이 되기 때문에 중앙을 지나갈 수 있다. 그리고 다음 50도 중앙을 지나가기 때문에 50을 지나갈 수 있다. 그렇다면 답이 2일까? 아니다 하나만 지나가기 때문에 1이된다.

다른 예시로도 가능하다. [1,1,48,48,1,1] 에서도 만약에 3가지 값을 고르는데 이전과 같은 패턴이 나온다면 겹치게 될 것이 분명하다. 그렇기 때문에 정답을 구할때는 2를 나눠주는 것이 맞다.

1. 전체 주어진 숫자의 조합을 따진다.

2. 그 조합에 맞춰서 0번부터 50이 되는 값을 구한다.

3. 그중 최고 많은 50을 만들 수 있는 조합을 찾아낸다.

4. 정답에서 2를 나눈다.

아래는 정답 코드이다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n;
vector<int> chart;

void init() {
	
	cin >> n;
	
	for(int i = 0; i < n; i++){
		int number; cin >> number;
		chart.push_back(number);
	}
	
	sort(chart.begin(), chart.end());
}

int solve(vector<int> chart) {
	
	int cnt = 0;
	int len = chart.size();
	
	for(int i = 0; i < chart.size(); i++){
		int sum = 0;
		int idx = i;
		
		while(sum < 50){
			sum += chart[idx];
			idx = (idx + 1) % len;
		}
		
		cnt += (sum == 50);
	}
	
	return cnt;
}

int main(){
	
	init();
	
	int answer = 0;
	
	do{
		answer = max(answer, solve(chart));
	}while(next_permutation(chart.begin(), chart.end()));
	
	//cout << "normal answer : " << answer << "\n";
	cout << answer / 2;
}