dbwjd7wkd   2년 전

문제 지문에서 ai + aj = x (1 ≤ i < j ≤ n)가 아니라 ai + aj = x (1 ≤ ai < aj ≤ n) 로 수정되어야 할 듯 합니다.

djm03178   2년 전

i, j가 맞습니다.

wizardrabbit   2년 전

기존 지문의 서술이 맞는 것으로 보입니다.

기존 지문

$$a_i + a_j = x\quad(1 \le i < j \le n)$$

  • 기존 지문의 서술에서의 제한 조건인 $1 \le i < j \le n$의 의미는 고르는 수열의 값의 인덱스가 범위를 벗어나면 안 된다는 것을 의미합니다. $i$, $j$의 대소 관계와 별개로 값이 $1$ 이상 $n$ 이하이므로 이는 "뭘 고르든 $1$번째~$n$번째 원소만 사용해라" 라는 의미가 되는 것이죠. 수열의 크기가 $5$인데 범위를 벗어나는 $999$번째 원소를 고르는 경우는 생각하지 않겠다는 뜻이 됩니다.

제안해 주신 지문

$$a_i + a_j = x\quad(1 \le a_i < a_j \le n)$$

  • 이 경우에는 어떤 두 원소를 고르든 그 원소의 값은 $1$ 이상 $n$ 이하여야 한다는 뜻이 됩니다. 기존 지문의 인덱스와는 이야기가 다릅니다.
  • 이 지문대로라면, $a = [5, 6, 7, 8]$, $x = 11$인 경우 답은 $0$이어야 합니다. 유일하게 두 원소의 합이 $11$이 되는 경우는 $5$와 $6$을 고르는 경우뿐인데, $5$와 $6$은 $n$의 값인 $4$보다 크기 때문에 답으로 채택할 수 없기 때문입니다. 하지만 문제의 의도는 그렇지 않습니다. 합이 $x$만 된다면 수열의 두 값을 골라 $x$를 만들 수 있는 경우를 고려하는 문제입니다.

예제 1번을 통한 확인

예제 $1$번의 경우 $n = 9$, $a = [5, 12, 7, 10, 9, 1, 2, 3, 11]$, $x = 13$입니다. 답이 $3$인데, 이는 만족하는 순서쌍이 $(12, 1)$, $(10, 3)$, $(2, 11)$이기 때문입니다. 이 중 순서쌍에 든 원소의 값은 당연히 $n$을 넘는 경우도 있습니다.

dlektkfkd   1년 전

@wizardrabbit 님 말씀 대로라면, 

ai + aj = x(1<=i<j<=n) 의 표시는 i, j 가 인덱스 이내이면 된다는 것은 이해했습니다만,

다른 한 편으로, ai>aj 이든, ai<aj 이든 문제 푸는데는 상관이 없어서(쌍) 문제에서 i<j라고 해도 괜찮은건가요??

그렇다면, i>j 인 경우는 문제의 답이 될 수 없는게 맞나요? 

인덱스의 값이 항상 i < j 여야 한다는게 한편으로는 문제 이해에 오해의 소지가 있다고 느껴집니다. 

djm03178   1년 전

상관이 없다기보다는 오히려 조건이 없으면 문제가 의미하는 바가 달라지므로 반드시 있어야 하는 조건입니다. 문제에서 요구하는 것은 같은 인덱스 쌍에 대해서 한 번만 카운트를 해야 하는 것인데, 인덱스의 대소 관계가 바뀌어도 된다면 (작은 인덱스, 큰 인덱스)와 (큰 인덱스, 작은 인덱스)를 모두 세어야 하므로 답이 기존의 2배가 됩니다. 게다가 i=j인 경우도 이 문제에서는 세지 않지만, 인덱스의 대소 관계가 없으면 세어주어야 합니다.

dlektkfkd   1년 전

@djm03178 님, 


덕분에 완전히 이해했습니다. 

감사합니다! 

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