다음 프로그램이 출력하는 수를 구하여라.
const int n = 10;
int b[n] ={1,4,5,7,8,10,11,12,14,15};
int i, p, r = 0;
for (p = 0; p < (1 << n); p++){
int x = 0;
for (i = 0; i < n; i++){
if (p & (1 << i)) x ^= b[i];
}
if (x <= 9) r++;
}
printf ("%d\n",r);
P는 0~(이진수 10000000000) 1024 까지 반복 한다.
P=00000000000 일 때 r=1
P=00000000001 일 때 x=1 r=2
P=00000000010 일 때 x=4 r=3
P=00000000011 일 때 x=1^4 = 5 r=4
P=00000000100 일 때 x=5 r=5
P=00000000101 일 때 x=1^5=4 r=6
P=00000000110 일 때 x=4^5=1 r=6
P=00000000111 일 때 x=1^4^5=0
P=00000001000 일 때 x=7
이렇게 1024번을 계산 하려고 하면 몇날 몇일 이 문제 한문제만으로 날밤을 세워야 할것 같네요.^^
따라서 규칙을 찾아야 하는 문제입니다.
먼저 비트 연산이므로 b 배열의 값을 이진수로 변환하면 다음과 같습니다.
b[] = {'0001','0100','0101','0111','1000','1010','1011','1100','1110','1111'}
이것을 P의 값을 이진수로 변환해서 P의 값이 1인 위치의 값을 xor 하면서 9보다 작거나 같은 경우를 구하는 문제입니다.
가령 P=00000000000(0) 일때는 10개의 데이터 중에 하나도 선택하지 않은 경우이므로 x=0 이 나옵니다.
P=00000000001(1) 일때는 10개의 데이터 중에 0번째 배열의 데이터('0001')를 선택 하는 경우 이므로 x=1 이 나옵니다.
P=00000000011(3) 일때는 10개의 데이터 중에 0번째('0001') 와 2번째 배열의 데이터('0100')를 선택 하여 xor 를 함으로 '0101'(5) 가 됩니다.
이런 방법으로 1의 위치에 있는 데이터를 선택해서 xor 한 후에 9('1001') 보다 작거나 같은경우 선택하면 되는 데요...
p의 값이 0 부터 1023 까지 순차적으로 올라가기 때문에 10비트의 숫자는 동일하게 512회씩 선택을 받게 되는 구조 입니다.
이런 경우 다이나믹 테이블을 이용해서 풀어 볼수가 있는데요...
가령 {1,4,5,7,8,10,11,12,14,15} 의 데이터 중에서
아무것도 선택하지 않은 경우 위의 0 에서 왼쪽 0 이라는 숫자를 만들 수 있습니다.
그리고 1을 선택해서 그 이전에 아무것도 선택하지 않은 경우 00(0000)와 xor 를 하면 01(0001)을 만들 수 있습니다. 따라서
(00(0000),00(0000)) 위치의 1이 (01(0001),01(0001) ) 위치로 갯수가 넘어 옵니다.
이것을 테이블로 만들어 보면 다음과 같은 형태로 나타낼 수가 있습니다.
+ 의 의미는 그 이전의 갯수를 현재 칸으로 가져온다는 의미 이고 화살표의 의미는 그 이전의 값과 현재의 값을 xor 한 경우 넘어 오는 형태를 표시 한것입니다.
이런식으로 테이블을 작성해서 보면 마지막 15를 선택했을때는 0 부터 15까지 모든 경우가 동일하게 64번씩 나오는 것을 확인할 수가 있네요.
그러면 0부터 9까지 10개의 수이므로 64 * 10 = 640 이 나온다는 것을 확인 할 수가 있었습니다.
정답은 640이 나옵니다.
풀이 과정이 쉽게 생각이 나지 않아서 학생들과 함께 머리 맞대고 고민을 많이 했던 문제였네요.^^
'강의자료 > 정보영재' 카테고리의 다른 글
정보올림피아드 문제 풀이 리스트 정리 (6) | 2018.06.28 |
---|---|
2018년 정보올림피아드 지역예선 중등부 15번 카탈란수 관련 문제 풀이 (2) | 2018.06.08 |
다항식의 곱셈공식을 활용한 문제 풀이 (3) | 2018.05.17 |
정보올림피아드 전국대회에서 장려상 확보하는 방법(0점을 면하는 방법) (3) | 2018.05.02 |
2004년 정보올림피아드 전국대회 초등 2번 줄자접기 문제 풀이 (3) | 2018.04.21 |