8-W 줄서기

Question

안녕하세요. 큰돌 강사님, 해설이 이해가 되지 않아서 질문 드립니다. 역사 문제와 이 문제의 풀이 방법이 왜 다른 건지 궁금합니다. 역사 문제의 경우 플로이드 워셜로 풀었었는데, 사건들의 전후 관계를 알고 있으니 , 역사 문제도 현재 풀이처럼 v[a]++, v[b]--; 로 풀면 안되나요?? 아래 코드가 전혀 이해가 되지 않습니다.. 앞에 있는 학생의 점수를 키우고, 뒤에 있는 학생은 줄이면 어떻게 1~N까지 카드 숫자를 나눠 갖나요?? for (int i = 0; i < m; i++) { cin >> a >> b; v[a]++, v[b]--; } for (int i = 1; i <= n; i++) { v[i] += i; visited[v[i]]++; } 감사합니다 좋은 하루 보내세요

큰돌 · Answer

안녕하세요 코테님 ㅎㅎ 역사 문제도 현재 풀이처럼 v[a]++, v[b]--; 로 풀면 안되나요?? >> 가능할 것 같습니다만 좀 어려울 것 같긴 합니다. 역사 문제는 전체쌍 출력이 아니라 순서쌍 쿼리이기 때문에 해당 부분을 고려하는 로직이 더 필요하고.. 역사 문제는 초기의 기본순서가 없기 때문에 해당 부분도 고려한 코드가 달라지는 점이 있을 것 같습니다. 참고로 줄서기 문제는 플로이드워셜로는 불가능합니다. (N자체가 너무나 크기 때문에) 앞에 있는 학생의 점수를 키우고, 뒤에 있는 학생은 줄이면 어떻게 1~N까지 카드 숫자를 나눠 갖나요?? >> 일단 문제를 보시면 "일렬로 서 있는 5명의 학생들을 앞에서부터 순서대로 “학생1, 학생2, 학생3, 학생4, 학생5”라고 하고" 처음에 일렬로 서있습니다. 그 다음... 예를 들어 1 2 1 3 2 3 이렇게 주어졌을 때 3 2 1 이 정답이죠? v[1] = 2 v[2] = 0 v[3] = -2 가 되는데요. ++ 와 --를 하는 부분은 가중치를 증감시킨다라고 보시면 됩니다. 예를 들어 우리가 A가 B보다 앞에있어! 라고 했을 때 이를 오름차순 정렬해서 표현한다고 하면... A를 --하고 B를 ++하면 오름차순 정렬시 A가 B보다 앞에 있게 되죠? 그부분을 생각하면 됩니다. 그 다음에 + i를 통해 v[1] = 3, v[2] = 2, v[3] = 1 가 됩니다. 이는 문제지문 "일렬로 서 있는 5명의 학생들을 앞에서부터 순서대로 “학생1, 학생2, 학생3, 학생4, 학생5”라고 하고" 이 부분 때문에 기존의 순서를 기반으로 해야되서 해당 부분을 추가하게 되는 것이죠. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.