이문제는 USACO 라는 대회의 문제를 그대로 가지고 온것이니 않될것 같내요 ㅎㅎ
2399번 - 거리의 합
이문제는 USACO 라는 대회의 문제를 그대로 가지고 온것이니 않될것 같내요 ㅎㅎ
@leoking042455님, USACO의 문제는 '영어로 된 원문'이고, 제가 처음에 적었듯 거기에는 n*(n-1)로 되어 있습니다. (정확히는 N*(N-1)이네요. 하지만 번역본에서는 N 대신 n을 썼으니 그렇게 적은 것입니다.)
제가 요청한 것은 '한글로 된 번역문'의 조건의 수정이니 충분히 말이 되는 요청이라 생각합니다.
인덱스가 i와 j가 서로 다르다는 언급은 없으며, 오히려 "모든 i, j에 대해서"는 당연히 i, j가 같을 때도 포함하는 표현이므로 모호함의 여지는 없어 보입니다.
서로 다르다는 언급이 없지만 같을 수 있다는 언급도 없습니다.
이런 상황에서 'i, j'로 분리해서 지정했기에 같을 수 있다는 언급이 별도로 없으면 다르다고 인식할 여지가 있습니다.
또한 '모든'이라는 표현 때문에 i, j가 같은 것을 포함한다고 하셨는데, 앞서 쌍이라고 표현되어 있어서, '쌍에 해당하는 모든 i, j들'이라고 생각하게 만듭니다
'쌍'이라는 표현은 기본적으로 '서로 다른 2개'를 묶는 표현입니다.
그렇기에 'n2'라는 표현을 빼고 보면 오히려 문제가 '서로 다른 2개의 점들로 구성되는 쌍들 간의 거리의 합'이라고 생각하기에 충분합니다.
제가 현재 시점에서 생각하는 결론은 다음과 같습니다.
한자 검색을 해봤는데, 원래 의미가 짝을 이루는 것이라고 합니다.
네이버 사전 검색 결과입니다.
https://hanja.dict.naver.com/#...
만약 동일한 것으로 짝을 이룰 수 있다면, 어떻게 그게 가능한 것인지 알고 싶네요.
수학적 의미로서의 쌍도 '같은 원소를 2번 고르는 경우'는 전혀 없습니다.
'같은 값을 2번 고르는 경우'와 헷갈리신 것 같네요.
예를 들어 4명의 학생의 수학 성적이 [20,20,30,50]이라는 배열(리스트)로 주어졌을 때를 생각해보겠습니다.
이런 경우, 동일한 값인 20이 2개 들어있습니다.
따라서 4명의 점수에 대한 점수 쌍을 만들 때 (20, 20)이라는 쌍이 생길 수 있습니다.
하지만, (30,30)은 동일한 학생을 2번 고른 것이며, 따라서 올바른 쌍으로 보기 어렵습니다.
정리하자면, 위의 예시에서 같은 값인 20 2개로 이뤄진 쌍이 생길 수 있지만 이는 서로 다른 2명의 성적을 고른 경우이므로 같은 원소인 20 2개로 이뤄진 쌍이 아닙니다.
게다가 처음 제가 수정 요청을 적은 글을 보면 원문에는 N*(N-1)을 쓰고 있다는 점도 같이 적었습니다.
결과적으로 답은 같을지 몰라도, 문제를 이해하는 데에 혼동이 올 수 있다고 생각했습니다.
그렇네요. 그래프의 경우에는 그런 표현을 쓰는군요.
뭐, 앞서 언급하지는 않았지만 이 문제의 경우 어느 쪽을 쓰든 답에는 영향이 없기도 하고요.
이제 비슷한 의문을 누군가 갖게 된다면 충분히 해소할 수 있을 것 같네요.
적어도 저는 어느 정도 납득했습니다.
이왕 이렇게 된 거, 여기에 제가 생각한 풀이법이나 적고 가겠습니다.
- 1번 점과 2번 점 사이의 거리가 a1라고 하자.
- 2번 점과 3번 점 사이의 거리가 a2라고 하자.
- 1번 점과 3번 점 사이의 거리는 a1+a2이다.
- 1~3번 점까지, 작은 번호로부터 큰 번호로의 거리의 합은 a1+(a1+2*a2)이다. (A1=a1, A2=a1+2*a2)
- 3번 점과 4번 점 사이의 거리는 a3라고 하자.
- 1번 점과 4번 점 사이의 거리는 a1+a2+a3이다.
- 2번 점과 4번 점 사이의 거리는 a2+a3이다.
- 1~4번 점까지, 거리의 합은 a1+(a1+2*a2)+(a1+2*a2+3*a3)이다. (A1=a1, A2=a1+2*a2,A3=a1+2*a2+3*a3)
- A1부터 AN-1까지의 합이 거리의 합이다. (정확히는 출력의 반이므로, 그 2배를 출력한다.)
댓글을 작성하려면 로그인해야 합니다.
adfsfsf 1년 전
지금 문제는 원문과 다르게 n2개의 값을 요구하고 있습니다.
하지만 일반적으로, 2개의 점을 고르라고 하면 서로 다른 2개의 점을 고르지 자기 자신을 고르지는 않잖아요?
원문에서처럼 n*(n-1)개로 수정해주는 것이 더 자연스러울 것 같습니다.