수다닷컴

질문 제목 : 2011 중등부 정올(모둠 문제)에 대한 알고리즘만이라도 알려주세요 ㅜㅜ 정말 긴 문제이기도 하고 읽기 귀찮으시겠지만 정말 몇일동안 고민했는데 모르겠어서 답답해서 물어봅니다 ㅜㅜㅜ

구체적인 소스가 아니어도 좋으니 대략적인 이론(알고리즘)만이라도 설명해주시면 감사하겠습니다 ㅜㅜ질문 내용 :
모둠문제는요,

koi대학교 영재교육원에서 정보올림피아드에 관심 있는 학생들을 위한 캠프가 열린다. 캠프에 모인 학생들 중에는 원래부터 서로 아는 사이인 경우가 있다.

교육원에서는 다음과 같은 방식으로 학생들을 몇 개의 모둠으로 분할하려고 한다.

먼저 학생들을 생년월일 순서대로 나열한 다음, 나열된 순서에서 연속된 구간에 속한 학생들을 하나의 모둠으로 구성할 것이다. 이 때, 분할을 위한 원칙은 다음과 같다.

각 모둠에 속한 학생들은 서로 아는 사이여야 하고, 다른 모둠에 속한 학생들과는 서로 모르는 사이여야 한다.

그러나 위의 원칙으로 분할하는 것이 불가능한 경우가 많다. 그래서 가능한 위의 원칙을 따르는 방향으로 분할을 수행하기 위해, 분할 점수라는 값을 도입하여 구성된 분할이 얼마나 좋은지를 평가한다. 분할 점수는 다음과 같이 구해진다.

같은 모둠에 속한 학생들 중에서 서로 모르는 학생 쌍에 대해 각각 1점씩 점수를 부여하고, 다른 모둠에 속한 학생들 중에서 서로 아는 사이인 학생 쌍에 대해 각각 1점씩 점수를 부여한다.

학생들에 대한 정보가 주어질 때, 분할 점수가 최소가 되는 분할을 구하는 프로그램을 작성하시오. 단, 모둠이 한 개만 있는 분할도 존재할 수 있다.
실행시간은 1초를 넘을 수 없다. 부분 점수는 없다
입력
첫째 줄에는 학생들의 수 n이 주어진다. n은 2 이상 3,000 이하이다. 학생들은 1부터 n까지 번호로 구분되고, 번호가 작은 학생은 번호가 큰 학생보다 생년월일이 빠르다. 둘째 줄부터 시작하여 n개의 줄에는 서로 알고 지내는 학생들에 대한 정보가 주어진다. 이들 중 k번째 줄에는 학생 k가 알고 있는 학생들의 번호와 끝을 나타내는 0이 빈칸을 사이에 두고 주어진다(k=1,2,...,n). 학생 번호들은 오름차순으로 주어진다. 학생 i가 학생 j를 알고 있으면, 항상 학생 j도 학생 i를 알고 있다. 출력
첫째 줄에 최적으로 분할한 경우의 분할 점수를 출력하고, 둘째 줄에는 모둠의 개수와 각 모둠의 크기를 빈칸을 사이에 두고 출력한다. 모둠은 생년월일이 빠른 학생들의 모둠부터 출력한다. 만일 분할 점수가 같은 분할이 여러 개 있으면 그 중 하나만 출력한다. 입출력 예입력82 3 01 3 4 01 2 4 5 02 3 5 03 4 6 05 7 8 06 06 0출력53 3 2 3

신청하기