정보올림피아드 2017년 지역대회 고등부 7번문제 풀이

오늘은 2017년 고등부 지역대회 문제를 풀어 보겠습니다.

문제

A, B, C, D, E가 처음 만나서 몇 명이 서로악수를 했다. 이 때, 악수를 한 두 사람의 쌍(순서쌍아님)들의 집합을 X라 하자. 적어도 한 쌍이 악수를 했고, 누구도 같은 사람과는 2번 이상 악수를 하지 않았다면 X가 될 수 있는 집합은 모두 몇 개인가?

2017년 초등부 문제에는 A,B,C 세명이 만나서 악수를 하는 문제가 출제 되었는데요...

이러한 문제는 집합의 멱집합 갯수를 파악하면 해결 되는 문제 입니다.

멱집합이란 어떤 집합의 모든 부분집합의 집합을 의미 하는데요...

가령 집합의 원소가 다음과 같이 {1,2,3} 와 같이 3개의 원소로 구성 되었다면.

멱집합은

{}(공집합),{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} 과 같이 8개의 부분집합을 만들수가 있습니다.

이러한 멱집합의 갯수는 원소갯수가 n 이라 하면 2의 n승에 해당하게 됩니다.

이러한 원리는 원소를 선택하거나 선택하지 않거나의 경우로 나누어 지기 때문에 1개의 원소에 따라 각각 2가지 경우가 존재 하므로 원소의 갯수가 3개라면 2 * 2 * 2 가 되는 것이거든요.

이러한 원리를 이용해서 A,B,C,D,E 가 악수를 할 수 있는 경우를 나타내 보면 다음과 같습니다.

(A,B).(A,C),(A,D),(A,E),(B,C),(B,D),(B,E),(C,D),(C,E),(D,E) 와 같이 10개의 원소로 이루어진 집합으로 보시면 됩니다.

이러한 집합의 멱집합 갯수는 2의 10승이며 1024 가지가 됩니다.

이때 적어도 한쌍 이상이 악수를 했다는 이야기는 공집합인 경우가 없다는 이야기 이므로 1가지를 뺀 1024 - 1 = 1023 가지가 됩니다.

초등부 문제에서는 직접 세어 볼수 있는 문제이지만...

고등부 문제에서는 원리를 파악하지 않으면 풀수 없었던것 같습니다.

멱집합이 무엇이고 멱집합의 갯수는 어떻게 구성되는지 원리를 알아 보는 문제 였습니다.

정보올림피아드 준비하는 학생들을 응원하며...

좋은 결과를 얻기를 바랍니다.

정보올림피아드 문제 풀이 리스트 정리