39. (3.4점) 다음 프로그램이 1 3 2 3 을 출력하도록 하 는 문자열 s의 개수를 구하여라. 단, s는 길이가 10이 며, ‘0’혹은 ‘1’로 이루어진 문자열이어야 한다.
프로그램을 해석하니 다음과 같은 수학문제가 되네요...
이렇게 일일히 규칙을 대입해서 만들어 보기는 했지만...
이렇게 대입해 보다 보면 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
'강의자료 > 정보영재' 카테고리의 다른 글
아이들에게 내 준 퀴즈 문제인데... 같이 한번 풀어 보시겠어요.^^ (6) | 2017.08.02 |
---|---|
NYPC2016 예선문제]넥슨은 다람쥐를 뿌려라 문제 분석 해 봤어요. (6) | 2017.07.27 |
2017년 정보올림피아드 예선 초등 22번 문제 분석 (6) | 2017.07.08 |
알고리즘 채점 사이트 정올(jungol.co.kr) 소개 (2) | 2017.06.23 |
소프트웨어 공부로 대학을 진학 할 수 있나요? (2) | 2017.06.09 |