[C++] SWEA 4408. 자기 방으로 돌아가기

1번부터 400번까지 복도를 사이에 두고 홀수 방과 짝수 방으로 나누어져 있으며 학생들이 현재 있는 방과 돌아가야 할 방을 입력으로 총 N개 받았을 때, 동선이 겹치는 학생은 동시에 이동할 수 없다고 한다. 이때 모든 학생이 전부 가야 할 방으로 돌아가려면 최소 몇 번의 이동이 필요한가? 출처 : SW Expert Academy 그리디로 풀이(잘못된 풀이) 한 번 이동할 때, 겹치는 구간 없이 이동할 수 있는 학생의 최대 집합을 계속 구해나가면서 해결하려 했다. 하지만 이 방식에는 여러 문제점이 존재했다. 동선이 겹치지 않고 움직일 수 있는 학생들의 집합 중 가장 큰 것은 여러 개 있을 수 있다. => 하나만 고려한다면 최소 횟수를 보장하지 않음 => 전부 다 고려하기에는 시간 복잡도가 매우 커짐 다른 방법을 아무리 생각해도 딱히 떠오르는 것이 없기에 정답 코드를 확인해 보았으며 보는 순간 깨달음을 얻었다. 구간 방문 횟수 카운트 복도 전체 구간으로 잡고 모든 학생이 한꺼번에 이동을...

원문링크 : [C++] SWEA 4408. 자기 방으로 돌아가기