[AlgoSpot] Picnic

問題を読む
Github Source

問題の概要

これは簡単な問題で、可能な友达が(もう半分)いる場合、それらを組み合わせて、学生にペアを組む場合の数を与えることができます.たとえば、次の2つのケースは、異なるケースでカウントされます.

(テヨン、Jessica)(Sunny、Tiffany)(孝淵、兪利)

(テヨン、Jessica)(Sunny、Yuri)(孝淵、Tiffany)

に答える

まず,生徒数が奇数であれば必然的に伴わない生徒が出現するため,解決策では直ちに戻る.奇数でない場合には,再帰法で問題を解決することが要求される.伴のある学生と伴わない学生を区別するために,isPairedboolean arrayに伴のある学生をtrueとし,伴のない学生をfalseとした.
再帰メソッドは、pairsarrayに格納されているペアリング可能なpairを入力の順序でループし、このpairarrayを使用してペアリングを作成すると、pairsarrayの次のインデックスpairarrayにも再帰メソッドがポーリングされ、このpairを使用してペアリングが作成されたかどうかを確認します.
たとえば、次のように入力したとします.

6 10

0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5

このとき、可能なパートナーを以下のように整理します.

(0,1)-0号

(0,2)-1号

(1,2)-2号

(1,3)-3号

(1,4)-4号

(2,3)-第5

(2,4)-6号

(3,4)-7号

(3,5)-第8

(4,5)-9号

まず,isPaired配列は初期時ともにfalseであり,0番pairを受け入れることを示す場合,isPaired[0]とisPaired[1]はtrueである.
また、次の1番pair、isPaired[0]がtrueであることを確認し、次のインデックスに移動します.
2番、3番、4番もisPaired[1]なので、次のインデックスに移動するときは、5番インデックスのpair(2,3)をチェックします.trueおよびisPaired[2]はisPaired[3]であり、同じテーブルがないため、両方ともfalseに変換され、次のindexのチェックを続行します.
このようにチェックした後、true配列がすべてisPairedであれば、trueを1だけ増やして返す場合がある.
すべてチェックしたが、Answer配列がすべてisPairedでなければ、すべてが伴うわけではないので、簡単に戻る.
次のようなコードがあります.

public void recursive(int pairIdx)
{
	// 모두 각자 짝이 있을 경우
	if (isAllTrue(isPaired))
	{
		Answer++;
		return;
	}
	// 모든 경우를 순회했을 경우
	if (pairIdx == pairs.length) return;

	// 둘 다 짝이 없는 경우
	// isPaired true로 할당 후 다음 pairIdx로 넘어감, return 후에는 원래대로 false로 할당
	if (!isPaired[pairs[pairIdx].pair1] && !isPaired[pairs[pairIdx].pair2])
	{
		isPaired[pairs[pairIdx].pair1] = true;
		isPaired[pairs[pairIdx].pair2] = true;

		recursive(pairIdx + 1);

		isPaired[pairs[pairIdx].pair1] = false;
		isPaired[pairs[pairIdx].pair2] = false;
	}

	// 어느 하나라도 짝이 있는 경우 - 다음 pairIdx로 넘어감
	recursive(pairIdx + 1);
}