강의실/정보영재

39. (3.4점) 다음 프로그램이 1 3 2 3 을 출력하도록 하 는 문자열 s의 개수를 구하여라. 단, s는 길이가 10이 며, ‘0’혹은 ‘1’로 이루어진 문자열이어야 한다.



프로그램을 해석하니 다음과 같은 수학문제가 되네요...


10자리 문자가 있는데 이 문자는 '0' 과 '1' 로만 이루어져 있습니다.

그런데 이 문자들은 다음의 규칙으로 이루어져 있습니다.
'00' 이 붙어 있는 경우가 1회
'01' 이 붙어 있는 경우가 3회
'10' 이 붙어 있는 경우가 2회
'11' 이 붙어 있는 경우가 3회 나오는 규칙으로 되어 있습니다.

모두 구해 보니 다음과 같이 30회가 나옵니다.


<1111 패턴 9개>
0010101111
0100101111
0101001111
0010111101
0100111101
0011110101
0111100101
0101111001
0111101001

<11 111 패턴 9개>
0010110111
0100110111
0011010111
0110010111
0101100111
0110100111
0011011101
0110011101
0110111001

<111 11 패턴 9개>
0010111011
0100111011
0011101011
0111001011
0101110011
0111010011
0011101101
0111001101
0111011001

<11 11 11 패턴 3개>
0011011011
0110011011
0110110011


이렇게 일일히 규칙을 대입해서 만들어 보기는 했지만...


이렇게 대입해 보다 보면 30개를 모두 찾아 낸다는것은 거의 불가능한 수준이라고 생각 되네요.^^



일단 010101 이 핵심 포인트입니다.

010101 은 01이 3 10이 2개 이므로 이 구조를 유지 하면서 이 구조에서 00 을 한개 111 을 이용해서 11을 3개를 만드는 구조입니다.


일단 010101 에서 00을 만드는 구조는 010101 의 빨간색 0 위치 옆에 0을 하나씩 두는 형태입니다. 그런데 00 이든 00 이든 동일한 형태 이므로 이것은 조합으로 3개 중에 하나를 선택하는 경우의 수이므로 3C1=3가지 경우가 됩니다. 0010101,0100101,0101001 과 같이요...


그리고 111 세개를 이용해서 010101의 위치를 이용해서 11을 세개를 만드는 경우인데요.

1의 위치 3군데에 1 세개를 선택해서 넣을 수 있는 경우의 수이므로 중복조합 형태인 3H3 의 경우의 수가 나옵니다.

1 세개를 010101 의 위치에 모두 넣을수도 있고...010101 에 2개 1개 또는 1개 2개 를 넣을수도 있으니까요...


중복조합 3H3을 계산하면 3+3-1C3 = 5C3 = 10 이 되고 00을 만드는 경우 3가지를 계산하면 다음과 같이 계산을 할 수가 있습니다.


3C1 * 3H3 = 3 * 10 = 30


위와 같이 계산하여 30이라는 숫자를 얻을수 있었습니다.


이 문제를 초등학생에게 풀으라고 하는건 좀 심해 보이는데요.

일단 조합 을 이용하지 않고도 규칙을 찾아서 해결 할 수도 있긴 할것 같은데요...


설명하는 입장에서는 조합의 규칙 을 이용한 풀이가 훨씬 쉽네요..ㅠ.ㅠ


순열,조합,중복조합의 원리 확인하러 가기 - http://wondangcom.com/311


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









이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
4 0