백준 #9020

★★☆☆☆☆☆☆☆☆

---

문제 접근 방식

이문제도 숫자 제한이 만까지 걸려있어서 만까지의 숫자를 모두 소수 판독을 한다. n이 입력되면 골드바흐 파티션을 구하기 위해 중간값을 기준으로 작은 값+큰 값이 n과 같을 때 1차 조건 충족, 충족했을 때의 둘의 차이를 저장해놓고 이 값이 최소인지를 비교하는 게 2차 조건. 이렇게 두고 문제 접근을 시작했다.

cin >> t;
	while (t--) {
		cin >> n;
		int mid = n / 2;    
		for (int i : decimal) { 
			if (i > mid)break; //비교할 두소수중 작은 소수를 고르기위해 중간값보다커지면 break
			total += i;   //total에 i넣고
			for (int j : decimal) {
				total += j;        //total에 j넣고
				if (total > n) { total -= j; break; } //두소수의 합이 n보다 커지면 다음단계로 넘어간다
				if (total == n) {
					temp = j-i;
					
					if (temp < sub) {
						answer1 = i;
						answer2 = j;
						sub = temp;
						
					}
				}
				total -= j;
			}
			total -= i;
		}
		cout << answer1 << " " << answer2 << "\n";
		sub = 9999;
	}

 처음풀때는 시간 초과가 발생해서 중간값을 기준으로 나누는 아이디어로 통과했다. 

이 코드의 풀이 방식은

1. i값을 total에 넣는다

2.j값을 total에 넣는다

3.total이 n과 같은지 비교한다. 
만약 같다면 두 수의 차이를 기록하고
만약 다르면 total에 바로 전 값을 빼준다.

4. 두 조건을 충족하는 수의 쌍 중에 차이가 최소인 수상을 출력한다.

시간 복잡도 O(n) 에라토스테네스의 체구현의 연산이 가장 많다.