문제는 https://projecteuler.net/problem=105
이전에 problem 106에서 사용한 unclear함수를 사용한다. - 문제 106번 보기
그리고 arr은 일종의 3진법이라 생각하면 될 것이다.
아래는 코드이다.
#ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #endif #include <stdio.h> #include <windows.h> #define N 12 bool check_rule2(int num[N], int n) { int i; int sumB = 0, sumC = 0; for (i = 0; i < n; i++) { if(i < n/2 + 1) sumB += num[i]; else sumC += num[i]; } return sumB > sumC; } int count(int arr[N], int p) { int i, count = 0; for (i = 0; i < N; i++) { if (arr[i] == p) count++; } return count; } bool unclear(int arr[N], int pairs) { int i, j; int point = 0; bool first = true; i = N-1; j = N-2; int iter = 0; while (i >= 0 && j >= 0) { if (arr[i] != 1) { i--; continue; } if (arr[j] != 2) { j--; continue; } if (i < j) { if (first) { return false; } point++; } first = false; i--; j--; } return point != 0 && point != pairs; } void swap(int &x, int &y) { int t = x; x = y; y = t; } void sort(int *arr, int n) { int i, j; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (arr[i] > arr[j]) { swap(arr[i], arr[j]); } } } } void main() { int m[N]; int i, n, t, sumB, sumC; int cnt1, cnt2; int numbers[12]; char line[100]; char *token; bool satisfy; int satisfySum = 0; FILE *input = fopen("p105_sets.txt", "rt"); printf("input = %s\n", (input == NULL ? "NULL" : "OPENED")); while (fscanf(input, "%s\n", line) != EOF) { token = strtok(line, ","); n = 0; while (token) { numbers[n] = atoi(token); n++; token = strtok(NULL, ","); } sort(numbers, n); for (i = 0; i < n; i++) printf("%4d ", numbers[i]); printf("\n"); if (!check_rule2(numbers, n)) { printf("!!! oh no, unexpected case\n"); continue; } // initialize m for (i = 0; i < N; i++) m[i] = 0; satisfy = true; while (true) { m[0] ++; for (i = 0; i < N - 1; i++) { if (m[i] > 2) { m[i] = 0; m[i + 1]++; } } if (m[n - 1] > 1) { satisfy = true; break; } cnt1 = count(m, 1); cnt2 = count(m, 2); sumB = 0; sumC = 0; for (i = 0; i < n; i++) { if (m[i] == 1) sumB += numbers[i]; if (m[i] == 2) sumC += numbers[i]; } if (cnt1 >= 2 && cnt1 == cnt2 && unclear(m, cnt1)) { if (sumB == sumC) { for (i = 0; i < n; i++) { printf("%4d ", m[i]); } printf("\n"); printf("sumB = %d, sumC =%d\n", sumB, sumC); satisfy = false; break; } } if (cnt1 > cnt2 && sumB <= sumC) { satisfy = false; break; } if (cnt1 < cnt2 && sumB >= sumC) { satisfy = false; break; } } if (satisfy) { for (i = 0; i < n; i++) { satisfySum += numbers[i]; } printf(">> this case satisfies both rules!\n"); } } printf("satisfySum = %d\n", satisfySum); system("pause"); }
'Project Euler' 카테고리의 다른 글
Project Euler #55 (Lychrel numbers) (0) | 2016.09.19 |
---|---|
Project Euler #108 (Diophantine reciprocals I) (0) | 2016.09.09 |
Project Euler #106 (Special subset sums: meta-testing) (0) | 2016.09.09 |
Project Euler #103 (Special subset sums: optimum) (0) | 2016.09.09 |
Project Euler #104 (Pandigital Fibonacci ends) (0) | 2016.09.09 |
댓글