[백준 C++] 17103번: 골드바흐 파티션

17103번: 골드바흐 파티션

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

www.acmicpc.net

이전에 풀었던 골드바흐의 추측을 풀었다면 간단하게 풀수있는 문제...

여야했다.

속이 상한다 아주.. 그 이유를 찾기위해 시간을 오래 썼는데

문제는 이

for (int i = 1;i <= n / 2 ;i++) {
			if (!a[i] && !a[n - i])
				ans++;
		}

골드바흐에서 썼던 포문을 그대로 사용하였기 때문이였다.

우선 순서만 다른 한쌍의 파티션 즉 n = 10 이라 가정했을때 (3, 5), (5, 5), (5, 3) 이렇게 세쌍의 파티션이 나오지만

(3, 5)와 (5, 3)은 순서만 다른 같은 파티션으로 보아서 정답인 ans는 2가 된다. 이때문에 i의 값을 <= n / 2 로 제한해 주어야한다.

또한 골드바흐의 추측에서는 i의 초기값을 3으로 설정하고 증감값도 어차피 짝수는 나오지 않으므로 i += 2로 설정해주었e다.

이 문제에서도 그렇게 풀면 어느정도는 맞다고 생각을 했는데 n = 4가 들어왔을때 (2, 2)로 소수의 합인 파티션으로 표현가능하다. 따라서 i = 1 부터 증감식 또한 i++로 바꿔주었더니 정답이 나왔다.

예외인 경우는 하나밬에 없지만, 문제를 제출할때는 몇개가 맞고 몇개가 틀렸는지를 알려주지 않으므로 이 부분에 문제가 생겼는지 찾기가 쉽지 않았다.

계속 다른 부분을 조금씩 바꾸며 진행하였고 확실하게 이 사항만 문제인지 확인하기 위해

if (n == 4) {
			ans++;
		}

이부분만 추가해주고 밑에 포문은 골드바흐의 추측문제와 똑같이 제출하였더니 정답이 나왔다. 역시 4 하나만 문제였던것...

반복문의 범위를 정확하게 정해주는것 또한 시간낭비를 피할 수 있는 방법이다. 많은 교훈이 되었던 문제

올빼미 개발자