allmin9702   1년 전

두가지중 j < i  for 문 즉 아래코드는 정답이고 위코드는 틀렸다고 나옵니다.
상식적으로 이해가 안되서 여러가지 반례를 찾아봤지만 저는 역부족이었습니다.

왜 j 값을 i 로부터 +1 하고  N까지 돌리는 for 문 즉, 위의 코드는 틀렸는지 아시는 쌉고수분 반례찾으실수 있으실지

wizardrabbit   1년 전

안녕하세요, 첫 번째 코드가 틀리는 이유는 바로 $\mathrm{ans}$의 초깃값이 $0$이면서, $\mathrm{ans}$가 한 번도 갱신되지 않을 수 있기 때문입니다. 이 경우 $0$이 답으로 출력되어 틀리게 됩니다. 두 번째 코드 또한 $\mathrm{ans}$의 초깃값은 $0$이지만 $\mathrm{dp}$의 모든 값이 초기에 $1$로 초기화되기 때문에 $\mathrm{ans}$는 반드시 $1$ 이상의 값을 가지게 되므로 문제 없습니다.

반례는 아래와 같습니다.

입력:
5
1 2 3 4 5

정답:
1

출력:
0

allmin9702   1년 전

아.. 너무나도 감사합니다.. 이런반례가 존재했었군요.. GPT 보다 뛰어나십니다..!

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