진수를 활용한 경우의 수 구하기

N방향을 M번 선택하는 경우, M자리 N진수로 경우의 수를 나타낼 수 있다.

 

예를 들어, 상 하 좌 우 중 한 방향을 3번 선택 한다고 하면, 4의 3승의 가지수 가 나오는데, 

0부터 4의 3승 값까지 % 연산으로 1의 자릿수를 구하고, 진수로 나누어 1의 자릿수를 버리는 것을 3번씩 반복하면 된다.

 

		int num =1;
		for(int i=0; i<5; i++) {
			num*=4;
		}
		
		for(int i=0; i<num; i++) {
			int brute = i;
			for(int j=0; j<3; j++) {
				System.out.print(brute%4);
				brute /= 4;
			}
			System.out.println();
		}

 

 

결과

 

숫자가 거꾸로 출력되긴 하지만 모든 경우의 수를 구해야 할 때 유용하게 써먹을 수 있다. 

필요한 경우 배열에 거꾸로 담는 등 처리를 하여 사용하면 된다.

000
100
200
300
010
110
210
310
(생략)
123
223
323
033
133
233
333