[C++] 변수가 서로 독립적일때, backTracking의 대안

1. 서론 

BOJ 15683번 감시문제를 풀다 보면, cctv의 종류에 따라, 행동양식이 틀려진다. 

이때, 경우의 수를 따져 야하기 때문에 backtracking을 이용할 수 있지만, 이때 유용한 방법을 알아서 적는다. 

 

2. 본론

경우의수	cctv1(4제곱승)	cctv2(4의1승)	cctv3(4의0승)
0	0	0	0
1	0	0	1
2	0	0	2
...
...
...
62	3	3	2
63	3	3	3

만약에 이 문제에서 cctv가 4가지의 경우의 수가 있다고 가정하자. 

그렇다면, cctv의 개수가 3개라면 , 총 64가지의 경우의 수가 나온다. 

이럴 때는 4진수로 표현을 한다. 1 << cctv.size() ; right shift를 이용해서 , cctv의 개수가 3이면 1000이 된다. 따라서 64가지의 경우의 수를 다룰 수 있다. 

이것을 표로 표현하자면 위와 같다. 이때, int dx [4] = {1,0,-1,0} , int dy [4] = {0,1,0,-1}로 두어, 방향성을 계산할 수 있다. 

이때 경우의 수로 나온 39를 예로 들어보자. 

1. 39 % 4 = 3 --> 4의 0승 자리

2. 39/4 = 9 

3. 9 % 4 = 1 --> 4의 1승 자리 

4. 9 / 4 = 2 

5. 2 % 4 = 2 --> 4의 2승 자리 

따라서, cctv마다의 각기의 방향을 결정할 수 있다. 만약에 이렇게 방향성을 설정하지 않는다면, 함수를 일일이 다 만들고, 모든 경우의 수를 일일이 입력해야 한다.