8-W 줄서기

안녕하세요. 큰돌 강사님,
해설이 이해가 되지 않아서 질문 드립니다.

역사 문제와 이 문제의 풀이 방법이 왜 다른 건지 궁금합니다.
역사문제의 경우 플로이드 워셜로 풀었었는데, 사건들의 전후 관계를 알고 있으니 ,
역사 문제도 현재 풀이처럼 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]]++;

}

감사합니다
좋은 하루 보내세요

안녕하세요 코테님 ㅎㅎ

역사 문제도 현재 풀이처럼 v[a]++, v[b]--; 로 풀면 안되나요??

>> 가능할 것 같습니다만 좀 어려울 것 같긴 합니다.

역사 문제는 전체쌍 출력이 아니라 순서쌍 쿼리이기 때문에 해당 부분을 고려하는 로직이 더 필요하고.. 역사 문제는 초기의 기본순서가 없기 때문에 해당 부분도 고려한 코드가 달라지는 점이 있을 것 같습니다.

참고로 줄서기 문제는 플로이드워셜로는 불가능합니다. (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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변