아니 그래서 왜 틀렸는데ㅠㅠ 맞왜틀ㅠㅠ
가끔 백준이라던지, 프로그래머스라던지 이런 알고리즘 사이트에서 문제를 풀다 보면 예제도 다 통과했고 다른 사람들이 알려준 반례도 다 통과했는데 도대체 왜 틀렸는지 알 수 없는 문제들이 있습니다. (맞왜틀????)
그럴 때 진짜 답답해서 미쳐버릴 거 같은 심정으로 반례를 찾아 헤매는데 이게 참 찾기가 쉽지 않죠… 그래서 준비했습니다! 반례 생성기!
예제 생성 함수
우선 example()이라는 예제 생성 함수를 만든 뒤, 문제에 맞춰서 randint()으로 최소 값, 최대 값 주고 예제를 생성하면 됩니다.
원래 1<=K<=10,000, 1<=N<=1,000,000, 랜선의 길이는 <=2,147,483,647인데 그렇게 하면 변수 값이 너무 커지니 임의로 줄였습니다.
python
C
코드 실행 함수
이제 맞은 코드와 틀린 코드를 실행하는 함수를 만들어야 합니다.
맞은 답은 인터넷에서 정답 코드를 구해 만들면 되고, 틀린 답 실행하는 함수에다가 틀린 코드 집어넣어서 만들면 됩니다.
python
C
반례 출력
이제 반례 출력하는 함수를 만들면 끝입니다. ex라는 변수에 예제 생성 함수의 리턴 값을 담고, 그 예제로 맞은 코드와 틀린 코드를 실행하면 됩니다. 만약 둘의 리턴 값이 같을 경우 다시 실행하고, 아니면 반례를 출력하게 했습니다.
python
C
전체 코드
python
from random import randint
# 예제 생성
def example():
K = randint(1, 10)
N = randint(K, 20)
lines = [0] * K
for i in range(K):
lines[i] = randint(1, 1000)
return [K, N, lines]
# 맞은 답
def right_sol(K, N, lines):
s = 1
e = max(lines)
res = 0
while s <= e:
cnt = 0
m = (s+e)//2
for i in lines:
if i >= m:
cnt += i // m
if cnt < N:
e = m - 1
else:
res = m
s = m + 1
return res
# 틀린 답
def wrong_sol(K, N, lines):
s = 0
e = max(lines)
res = 0
while s <= e:
cnt = 0
m = (s+e)//2
for i in lines:
if i > m:
cnt += i // m
if cnt < N:
e = m - 1
else:
res = m
s = m + 1
return res
# 반례 출력
def check():
ex = example()
right = right_sol(ex[0], ex[1], ex[2])
wrong = wrong_sol(ex[0], ex[1], ex[2])
if right != wrong:
print(ex[0], ex[1])
for i in ex[2]:
print(i)
print("맞은 답:", right)
print("틀린 답:", wrong)
return
else:
check()
check()
Python
복사
C
#include <stdio.h>
#include <stdlib.h>
int K, N;
void example(void)
{
K = rand() % 100;
N = rand() % 100;
}
int incorrect(int K, int N, int lines[])
{
int start, end, res, mid;
start = 1;
end = 1;
while (1)
{
res = 0;
mid = (start + end) / 2;
for(int i = 0; i < K; i++)
{
res += (lines[i] / mid);
}
if (res < N)
end = mid - 1;
else
break ;
}
return (0);
}
int correct(int K, int N, int lines[])
{
int res;
int max;
long long int start = 1;
long long int end = 1;
long long int mid = 1;
while (1)
{
res = 0;
mid = (long long int)((start + end) / 2);
for(int i = 0; i < K; i++)
{
res += (lines[i] / mid);
}
if (res < N)
end = mid - 1;
else
{
max = mid;
start = mid + 1;
}
if (start > end)
break ;
}
return (max);
}
int main(void)
{
int right;
int wrong;
example();
int lines[K];
for(int i = 0; i < K; i++)
{
lines[i] = rand() % 100;
}
right = correct(K, N, lines);
wrong = incorrect(K, N, lines);
while (right == wrong)
main();
printf("예제: K = %d, N = %d\n", K, N);
printf("lines: ");
for(int i = 0; i < K; i++)
{
printf("%d ", lines[i]);
}
printf("\n");
printf("맞은 답: %d\n", right);
printf("틀린 답: %d\n", wrong);
return (0);
}
C
복사
알고리즘 공부 파이팅!!!
