경우의 수들을 진법으로 표현하는 방법에서 역방향으로 출력되는 경우에 대한 이해.

boj 15683 : 감시 

문제를 해결할때, 

가능한 경우들에 대해서 이걸 4진법의 수로 표현하는 방법에 대한 코드를 작성할때, 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int tmp=0; tmp<64; tmp++){
        int brute=tmp;
        for(int i=0; i<3; i++){
            cout<<brute%4;
            brute/=4;
        }
        cout<<'\n';
    }
}

이와같이 작성할 수 있는데, 

이때에 출력해보면, 출력물의 경우는 

000
100
200
300
010
110
210
310
020
120
220
320
030
130
230
330
001
101
201
301
011
111
211
311
021
121
221
321
031
131
231
331
002
102
202
302
012
112
212
312
022
122
222
322
032
132
232
332
003
103
203
303
013
113
213
313
023
123
223
323
033
133
233
333

 

이와같이 총 64가지의 값을 출력하게 된다. 

이 수들의 경우는, 

0을 4진수로 나타낼때 역방향으로, 

1을 4진수로 나타낼때 역방향으로(100이 출력되었는데, 뒤에서부터 001로 보면 이 수가 바로 1을 4진수로 나타낸 수와 같다)

2을 4진수로 나타낼때 역방향으로(200이 출력되었는데, 뒤에서부터 002로 보면 이 수가 바로 2을 4진수로 나타낸 수와 같다)

...

62를 4진수로 나타낼때 역방향으로(233이 출력되었는데, 뒤에서부터 332로 보면 이 수가 바로 62를 4진수로 나타낸 수와 같다)

63을 4진수로 나타낼 때 역방향으로(333으로 출력되었는데, 뒤에서부터 333로 보면 이 수가 바로 63을 4진수로 나타낸 수와 같다)

 

형태로 출력된 것이고, 각각의 수에서 하나하나의 수를

2중 for문에서 안쪽의 for문에 해당하는

        for(int i=0; i<3; i++){
            cout<<brute%4;
            brute/=4;
        }

로 출력한 각각의 값에 해당한다. 

 

다음에도 이렇듯 각각의 경우의 수가 독립적인 경우, 진법을 이용해서 각각의 수를 표현하면 백트래킹을 사용하지 않고 

각각의 경우의 수 들을 통해 케이스를 셀때 활용할 수 있다. 

이런 형태의 코드 형식에 익숙해지도록 하자.