강의실/정보영재

다음 프로그램이 출력하는 수를 구하여라.

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이 나옵니다.


풀이 과정이 쉽게 생각이 나지 않아서 학생들과 함께 머리 맞대고 고민을 많이 했던 문제였네요.^^



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





이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
2 0
  • 휴식같은 친구 2018.05.30 19:41 신고    

    이걸 수작업으로 하려면 정말 어려울건데 코딩으로 간단하게 하니 신기합니다.ㅎㅎ

  • 핑구야 날자 2018.05.31 06:48 신고    

    오늘 문제는 생각보다 어렵네요 즐거운 하루 보내세요