-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
8-W 줄서기
24.04.03 17:50 작성 24.04.03 17:52 수정 조회수 91
0
안녕하세요. 큰돌 강사님,
해설이 이해가 되지 않아서 질문 드립니다.
역사 문제와 이 문제의 풀이 방법이 왜 다른 건지 궁금합니다.
역사문제의 경우 플로이드 워셜로 풀었었는데, 사건들의 전후 관계를 알고 있으니 ,
역사 문제도 현재 풀이처럼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]]++;
}
감사합니다
좋은 하루 보내세요
답변을 작성해보세요.
0
큰돌
지식공유자2024.04.04
안녕하세요 코테님 ㅎㅎ
역사 문제도 현재 풀이처럼 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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
답변 1