자료구조&알고리즘
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
반응형