-
SWEA 3814 평등주의자료구조&알고리즘 2019. 10. 1. 16:08
FAIL한 최초 코드
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> // 사용가능한 라이브러리 여부 확인 /* 3814 평등주의 input) 2 5 5 4 2 3 7 6 5 4 4 2 3 7 8 output) #1 1 #2 2 문제 발견 5 3 7 3 4 5 6 하면 1이 나와야하는데 2가 나옴 2019.10.01 */ int main() { // unsafe error // https://bymakers.tistory.com/6 freopen("./input.txt", "r", stdin); // input int T, N, K; int t = 0; int i = 0; int start = 0; int end = 0; int middle = 0; int last_middle = 0; int temp_k = 0; scanf_s("%d", &T); for (t = 0; t < T; t++) { scanf_s("%d %d", &N, &K); // int numbers[N]; // 고정 크기의 배열일 때 사용 int *numbers = (int*)malloc(sizeof(int)*N); // 동적 할당 (int*) 을 붙이는 것과 안 붙이는 것의 차이? int* numbers_cp = (int*)malloc(sizeof(int) * N); // null 포인터를 역참조하고 있다는 에러 메세지 뜸 C6011 // https://pang2h.tistory.com/196 if (numbers != NULL) { for (i = 0; i < N; i++) { scanf_s("%d", &numbers[i]); } } int max_value = 0; // inital value for (i = 0; i < N-1; i++) { if ((numbers[i] - numbers[i+1]) >= max_value) { max_value = (numbers[i]-numbers[i+1]); } else if ((numbers[i+1] - numbers[i]) >= max_value) { max_value = (numbers[i+1] - numbers[i]); } } end = max_value; middle = (start + end) / 2 + (start + end) % 2; // main (binary search) while (1) { // test용 //printf("%d %d %d %d %d\n", numbers_cp[0], numbers_cp[1], numbers_cp[2], numbers_cp[3], numbers_cp[4]); // 돌 때마다 배열 복사 (이분 탐색 할 때마다 원래 배열 상태로 시작) for (i = 0; i < N; i++) { numbers_cp[i] = numbers[i]; } temp_k = K; last_middle = middle; // 돌면서 middle에 해당할 때까지 다 뺀다 for (i = 0; i < N-1; i++) { if ((numbers_cp[i] - numbers_cp[i+1]) > middle) { temp_k -= ((numbers_cp[i] - numbers_cp[i + 1]) - middle); numbers_cp[i] -= ((numbers_cp[i] - numbers_cp[i + 1]) - middle); } else if ((numbers_cp[i+1] - numbers_cp[i]) > middle) { temp_k -= ((numbers_cp[i+1] - numbers_cp[i]) - middle); numbers_cp[i+1] -= ((numbers_cp[i+1] - numbers_cp[i]) - middle); } } // 차이값을 더 크게 잡음 (이 범위에는 답이 없다) if (temp_k < 0) { start = middle; middle = (start + end) / 2 + (start + end) % 2; } // 차이값을 더 줄여도 됨! else { end = middle; middle = (start + end) / 2 + (start + end) % 2; if (middle == last_middle) { //max_value = middle; break; } } } // output printf("#%d %d\n", t+1, last_middle); } /* 동적 할당 https://mrsnake.tistory.com/45 */ return 0; }성공 코드와 FAIL 코드 비교
- 원래의 실패 코드는 한 번에 오른쪽과 내쪽을 비교하면서 for문을 돌고 끝내버린다. 그러면 맨 처음 요소가 단 한 번밖에 고려되지 않는다. 맨 앞을 다시 보지 않으면 원하는 차이값이 나오기 전에 K가 남았다는 사실을 인지하자마자 가능하다고 가정하고 끝내버린다! K가 부족할 수 있음. 이것을 확인하는 반례는
1
3 7
5 10 2
이다. 잘못 짠 코드는 1이 나오고 제대로 수정하면 2가 나온다.
- 성공 코드에서도 오른쪽으로 확인하는 for문에서 왼쪽 element를 감소시키고, 왼쪽으로 확인하는 다음 for문에서 오른쪽 element를 감소시키면 기본 예제인 4 2 3 7 6 만 비교해봐도 숫자를 제대로 감소시키지 않고 지나간다.
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <time.h> int pass_code(int N, int K, int* numbers) { int numbers_cp[100000]; int start = 0; int end = 0; int middle = 0; int last_middle = 0; int temp_k = 0; int i = 0; int max_value = 0; // inital value for (i = 0; i < N - 1; i++) { if ((numbers[i] - numbers[i + 1]) >= max_value) { max_value = (numbers[i] - numbers[i + 1]); } else if ((numbers[i + 1] - numbers[i]) >= max_value) { max_value = (numbers[i + 1] - numbers[i]); } } start = 0; // initialize end = max_value; middle = (start + end) / 2; last_middle = middle; // initialize // main (binary search) while (start <= end) { // test용 //printf("%d %d %d %d %d\n", numbers_cp[0], numbers_cp[1], numbers_cp[2], numbers_cp[3], numbers_cp[4]); // 돌 때마다 배열 복사 (이분 탐색 할 때마다 원래 배열 상태로 시작) for (i = 0; i < N; i++) { numbers_cp[i] = numbers[i]; } temp_k = K; middle = (start + end) / 2; // 돌면서 middle에 해당할 때까지 다 뺀다 for (i = 0; i < N - 1; i++) { if ((numbers_cp[i + 1] - numbers_cp[i]) > middle) { temp_k -= ((numbers_cp[i + 1] - numbers_cp[i]) - middle); numbers_cp[i + 1] -= ((numbers_cp[i + 1] - numbers_cp[i]) - middle); } if (temp_k < 0) { break; } } for (i = N - 1; i > 0; i--) { if ((numbers_cp[i - 1] - numbers_cp[i]) > middle) { temp_k -= ((numbers_cp[i - 1] - numbers_cp[i]) - middle); numbers_cp[i - 1] -= ((numbers_cp[i - 1] - numbers_cp[i]) - middle); } if (temp_k < 0) { break; } } if (temp_k < 0) { start = middle + 1; } // 차이값을 더 줄여도 됨! else { last_middle = middle; end = middle - 1; } } return last_middle; } int fail_code(int N, int K, int* numbers) { int numbers_cp[100000]; int start = 0; int end = 0; int middle = 0; int last_middle = 0; int temp_k = 0; int i = 0; int max_value = 0; // inital value for (i = 0; i < N - 1; i++) { if ((numbers[i] - numbers[i + 1]) >= max_value) { max_value = (numbers[i] - numbers[i + 1]); } else if ((numbers[i + 1] - numbers[i]) >= max_value) { max_value = (numbers[i + 1] - numbers[i]); } } start = 0; end = max_value; middle = (start + end) / 2 + (start + end) % 2; last_middle = middle; // main (binary search) while (1) { // test용 //printf("%d %d %d %d %d\n", numbers_cp[0], numbers_cp[1], numbers_cp[2], numbers_cp[3], numbers_cp[4]); // 돌 때마다 배열 복사 (이분 탐색 할 때마다 원래 배열 상태로 시작) for (i = 0; i < N; i++) { numbers_cp[i] = numbers[i]; } temp_k = K; // 돌면서 middle에 해당할 때까지 다 뺀다 for (i = 0; i < N - 1; i++) { if ((numbers_cp[i] - numbers_cp[i + 1]) > middle) { temp_k -= ((numbers_cp[i] - numbers_cp[i + 1]) - middle); numbers_cp[i] -= ((numbers_cp[i] - numbers_cp[i + 1]) - middle); } else if ((numbers_cp[i + 1] - numbers_cp[i]) > middle) { temp_k -= ((numbers_cp[i + 1] - numbers_cp[i]) - middle); numbers_cp[i + 1] -= ((numbers_cp[i + 1] - numbers_cp[i]) - middle); } } // k 범위를 넉넉하게 줘서 기준을 약하게 if (temp_k < 0) { start = middle + 1; middle = (start + end) / 2 + (start + end) % 2; } // k 범위를 줄여서 기준을 강하게! else { last_middle = middle; end = middle - 1; middle = (start + end) / 2 + (start + end) % 2; if (start > end) { break; } } } return last_middle; } int main(void) { // generate test case int test_case; int T = 200; int N, K; srand((unsigned)time(NULL)); for (test_case = 1; test_case <= T; ++test_case) { // 생성 N = rand(); K = rand(); printf("N: %d K: %d ", N, K); // input int i = 0; int start = 0; int end = 0; int middle = 0; int last_middle = 0; int temp_k = 0; // int numbers[N]; // 고정 크기의 배열일 때 사용 int numbers[100000]; //int* numbers = (int*)malloc(sizeof(int) * N); // 동적 할당 (int*) 을 붙이는 것과 안 붙이는 것의 차이? //int* numbers_cp = (int*)malloc(sizeof(int) * N); // null 포인터를 역참조하고 있다는 에러 메세지 뜸 C6011 // https://pang2h.tistory.com/196 if (numbers != NULL) { for (i = 0; i < N; i++) { numbers[i] = rand(); // printf("%d ", numbers[i]); } } int max_value = 0; int pass_ans = pass_code(N, K, numbers); int fail_ans = fail_code(N, K, numbers); // output if (pass_ans == fail_ans) printf("#%d True\n", test_case); else { printf("#%d False: pass ans %d fail ans %d", test_case, pass_ans, fail_ans); } } return 0; //정상종료시 반드시 0을 리턴해야 합니다. }문제가 있지만 통과된 코드
- lo = 0; 초기화를 해야한다. 지금 차이값들보다 더 작아질 수 있기 때문에
- return false; for문 가장 마지막으로 내려서 K값을 만족한 것이 맞는지 마지막 요소까지 포함해서 확인을 해야한다.
#include <iostream> using namespace std; #define MAX 1000000007 #define MIN -1 int tc, T, N, K, A[100001], _A[100001]; int ABS(int v) { return v > 0 ? v : -v; } bool conf(int c) { int cnt = 0; for (int a = 0; a < N; a++) _A[a] = A[a]; for (int a = 0; a < N - 1; a++) { if (cnt > K) return false; if (_A[a] + c < _A[a + 1]) { cnt += (_A[a + 1] - (_A[a] + c)); _A[a + 1] = _A[a] + c; } } for (int a = N - 1; a > 0; a--) { if (cnt > K) return false; if (_A[a] + c < _A[a - 1]) { cnt += (_A[a - 1] - (_A[a] + c)); _A[a - 1] = _A[a] + c; } } for (int a = 0; a < N - 1; a++) { if (cnt > K) return false; if (_A[a] + c < _A[a + 1]) { cnt += (_A[a + 1] - (_A[a] + c)); _A[a + 1] = _A[a] + c; } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> T; for (tc = 1; tc <= T; tc++) { cin >> N >> K; int lo = MAX, hi = MIN; for (int a = 0; a < N; a++) { cin >> A[a]; if (a > 0) { int tmp = ABS(A[a] - A[a - 1]); if (lo > tmp) lo = tmp; if (hi < tmp) hi = tmp; } } int ans = -1; while (lo <= hi) { int mi = (lo + hi) / 2; if (conf(mi)) ans = mi, hi = mi - 1; else lo = mi + 1; } cout << "#" << tc << " " << ans << "\n"; } return 0; }문제가 없었던 코드
- 이분탐색 방식에 대한 내용 (https://ilyoan.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%EA%B8%B0%EB%B2%95-4-%EB%B0%94%EC%9D%B4%EB%84%88%EB%A6%AC%EC%84%9C%EC%B9%98)
#include<iostream> #define MIN (0) #define MAX (1000000000) using namespace std; int A[100000]; int B[100000]; int K, T, N; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("./input.txt", "r", stdin); cin >> T; for (int test = 1; test <= T; ++test) { cin >> N >> K; for (int i = 0; i < N; ++i) { int tmp; cin >> tmp; A[i] = tmp; } int min = MIN, max = MAX; int ans = 0; while (min < max) { int k = K; int mid = (min + max) / 2; bool check = true; for (int i = 0; i < N; ++i) B[i] = A[i]; for (int i = 0; i < N - 1; ++i) { int diff = B[i + 1] - B[i]; if (diff > mid) { B[i + 1] -= diff - mid; k -= (diff - mid); if (k < 0) { check = false; break; } } } for (int i = N - 1; i > 0; --i) { int diff = B[i - 1] - B[i]; if (diff > mid) { B[i - 1] -= (diff - mid); k -= (diff - mid); if (k < 0) { check = false; break; } } } if (!check) { min = mid + 1; ans = min; } else { max = mid; } } cout << "#" << test << " " << ans << '\n'; } return 0; }d
'자료구조&알고리즘' 카테고리의 다른 글
SWEASS H1921 여행상품추천 (0) 2019.10.16 BOJ 16637 괄호 추가하기 (0) 2019.10.11 동적 계획법 (Dynamic Programming) (0) 2019.08.14 원격 데이터 베이스 구성하기 - 2 (MariaDB 설치) (0) 2019.07.23 CS186 Introduction to Database systems (1강 - intro) (0) 2019.07.15 댓글