글 읽기 - [파이썬] 반례를 찾고 싶습니다!

rlaehdgks12 2년 전 0

항상 궁금 했던점이 있습니다

선배님들은 어떻게 반례를 찾으시나요?

수를 대입하는 기준이 있으신가요?

아님 막 대입해 보나요?

반례찾는 팁좀 부탁드립니다.

이 문제에 대한 반례는

어떤 근거로 찾으셨는지 설명해주시면 감사하겠습니다.

N,K = map(int,input().split())
llist = []
sum = 0
EV = 0
EV_list = []
for _ in range(N):
  W,V = map(int,input().split())
  llist.append([W,V])
for i in range(len(llist)):
  sum = 0
  EV_list.append(EV)
  EV = 0
  for j in range(i,len(llist)):
    sum += llist[j][0]
    if sum > K:
      sum -= llist[j][0]
      continue
    EV += llist[j][1]
EV_list.sort()
print(EV_list[-1])

  

314programs 2년 전 1

반례:

1 2
1 3

답: 3

출력: 0

코드에 약점?을 보고 대입하는 편.

저는 코너 캐이스를 자주 찾거나(이번 경우), 개시판을 보고 반례를 찾아요.

rlaehdgks12 2년 전 0

감사합니다!

ai4youej 2년 전 2

1. 일단 코드를 쭉 읽어보고, 어떤 코드가 문제인거 같으면 그것을 저격할 수 있는 데이터를 만들어봅니다

2. 코너 케이스의 경우를 넣어봅니다

3. 노가다를 합니다

lcr7324 2년 전 4

0. 게시판에 이미 올라온 반례를 다 넣어봅니다.

1. 코너 케이스를 넣어봅니다 (예컨대 N 제한이 1 이상 1000 이하라면 1, 2인 경우와 1000인 경우 등)

2. 이 문제에서는 해당하지 않지만, 문제 구성 상 직접 유효한 입출력 쌍을 만들기가 쉬운 경우가 있습니다. (출력을 기반으로 입력을 만들 수 있는 경우) 이 경우는 직접 랜덤 함수를 기반으로 입출력 데이터를 잔뜩 생성해서 반례를 찾아봅니다.

3. 시간 복잡도 때문에 시간 초과를 받지만 옳은 답을 내는 (혹은 그렇다고 추정되는) 코드를 작성할 수 있다면, 두 코드가 다른 답을 낼 때까지 랜덤 데이터를 넣어봅니다.

4. 문제 출처에 따라 인터넷에 입출력 데이터가 공개된 경우가 있습니다. 이런 데이터를 찾을 수 있다면 찾아서 넣어봅니다.

5. 여기까지 해도 안된다면 죽어라 디버깅하는 수밖에 없습니다. 코드의 모든 실행 과정을 따라가며 ~~까지 실행됐을 때 ~~변수의 상태는 이러할 것이라 추정하고, 실제로 그런지 중간 과정을 다 출력해보며 따라가봅니다. 문제를 다시 꼼꼼히 읽으며 1번에서 놓쳤을지도 모르는 코너 케이스를 찾으려 노력합니다.

6. 한숨 자고 다음 날 봅니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 반례를 찾고 싶습니다!

rlaehdgks12 2년 전 0

314programs 2년 전 1

rlaehdgks12 2년 전 0

ai4youej 2년 전 2

lcr7324 2년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말