[컴퓨팅사고력]컨테이너 적재하기

한 항구에 적재 되어야 할 많은 컨테이너가 있습니다.

이 컨테이너들은 색상을 가지며 이 색상에 의해 컨테이너의 종류가 구분되어 집니다.

각 색상은 컨테이너 종류를 나타내기 위한것입니다.

다음과 같이 10개 색상의 컨테이너가 있고 준비된 컨테이너들 중 2개의 컨테이너를 타이타닉호에 적재해야 됩니다.

(빨,빨,빨,파,파,노,노,노,주,검)

원당이는 이것을 적재하는 경우의 수가 몇가지인지 궁금합니다.

원당이를 위해 모든 경우의 수가 몇가지인지 구해 주세요.

 

정답) 13가지

경우의 수)

빨,빨

빨,파

빨,노

빨,주

빨,검

파,파

파,노

파,주

파,검

노,노

노,주

노,검

주,검

문제풀이)

이러한 문제는 조합론에 기본을 둔 문제로 다양한 방법의 경우의 수를 구하는 문제입니다. 각각 중복이 가능하면서 순서가 없는 조합을 구하는 것이 핵심이 됩니다. 

모두 다른 색이라면 10C2 = 10*9/2 = 45 가지가 되겠지만

여기서는 같은 색이 여러개 있기 때문에 중복 되는 경우를 제거해야 됩니다.

첫번째 빨강을 선택했을때 두번째 선택방법 5가지

첫번째 파랑을 선택했을때 두번째 선택방법 4가지

...

처럼 각각 구해 주어야 합니다.

 

컴퓨팅 사고력

위와 같은 유형의 문제는 경시대회와 같은 알고리즘 문제 유형에서 종종 볼 수 있는 문제유형입니다.

이러한 문제는 컴퓨팅사고력에서 백트래킹 기법을 활용해서 첫번째 빨강을 놓아 보고 그 다음 빨강 부터 모든것을 다 놓아 봅니다.

그리고 그 다음에 빨강 색을 놓아 보고 그 다음 다시 또 놓아 보면서 이미 같은 색을 선택했다면 경우의 수를 제거하는 형식으로 문제를 풀어 볼 수가 있습니다.