POJ - 4004: 디지털 조합 (변위 방법 으로 조합 수 문 제 를 풀 고 자바 버 전)

개요:
    문 제 를 보고 나 면 이 문 제 는 하나의 조합 수의 사고 로 코드 를 만 들 수 있다 는 것 을 생각 하 게 될 것 이다.즉, 우 리 는 제 시 된 배열 에서 몇 개의 수 를 무 작위 로 추출 하고 더 한 것 과 더 해 야 할 것 은 제 시 된 그 수 와 같다 는 것 이다.비록 대체적인 사상 은 틀 리 지 않 았 지만, 구체 적 인 사고방식 은 어 떻 습 니까?
사고 분석:
    우 리 는 컴퓨터 에 이 1 차원 배열 의 특정한 위치 가 내 가 선택 하고 자 하 는 숫자 라 는 것 을 알려 주 는 일반적인 방법 이 있 을 까?
모두 가 생각 할 수 있 는 것 은 재 귀 일 것 이다. 그러나 나의 한 친 구 는 나 에 게 또 다른 생각 을 주 었 다. 그것 은 바로 변위 로 이 문 제 를 해결 하 는 것 이다.왜 변위 해? 빠 르 니까!
    이 안 에는 작은 기교 가 하나 있 는데 그것 이 바로 1 < n 은 2 와 같은 n 차방 (예 를 들 어 1 < 5 = 32) 이다.즉, 1 을 n 자리 로 옮 기 면 여기 서 결 과 를 얻 을 수 있다. 이 결 과 는 바로 우리 1 차원 배열 의 모든 부분 집합, 즉 모든 조합 수 이다.
    사실 만약 당신 이 숫자 가 컴퓨터 에 저장 되 고 증가 하 는 과정 을 이해한다 면, 당신 은 재 미 있 는 결론 을 얻 을 수 있 을 것 입 니 다. 그것 은 바로 내 가 0 (공 집) 에서 1 < n 까지 이 숫자 들 이 대표 하 는 것 은 바로 우리 가 컴퓨터 가 그 자리 에 우리 가 남 겨 야 하 는 것 이 고, 그 자리 의 수 는 우리 가 필요 로 하지 않 는 것 이 라 고 알려 주 는 것 입 니 다.컴퓨터 에 숫자 가 저장 되 고 증가 하 는 과정 에 대해 서 는 설명 하지 않 습 니 다.관심 있 는 친 구 는 관련 자 료 를 찾 아 볼 수 있다.
    이상 은 단지 모든 조합 수 를 얻 었 을 뿐이다.그리고 그들 도 모두 하나의 숫자 로 대표 된다. 그러면 우 리 는 특정한 조작 이나 계산 을 통 해 표지 배열 이나 특정한 그의 무엇 을 얻 을 수 있 는 지 설명 할 수 있 을 까? 현재 배열 의 i 위 는 필요 한 것 일 까?하나의 숫자 가 대표 하 는 어떤 조합 만 으로 는 컴퓨터 가 우리 가 필요 로 하 는 위치의 값 을 완전히 이해 할 수 없 기 때문이다.
다음은 우리 가 숫자 5 가 있다 고 가정 하면 우 리 는 이 숫자 5 가 대표 하 는 조합 을 어떻게 얻어 야 합 니까?
0
1
0
1
0
0
0
1
위의 표 의 첫 줄 은 숫자 5 이 고 두 번 째 줄 은 숫자 1 이다.
우리 가 지금 가설 문제 에서 우리 에 게 알려 준 것 은 네 개의 숫자 밖 에 없다.
그러면 우 리 는 먼저 a & 1 의 값 (& 위치 이 고 조작 부호 입 니 다. 그 역할 은 두 개의 수의 모든 바 이 너 리 의 값 이 1 일 때 이 위치의 값 이 1.......................................................
이렇게 하면 우 리 는 첫 번 째 표 에서 숫자 1 을 얻 을 수 있 고 우 리 는 그것 을 b [0] 에 저장 할 수 있다.
이때, a 오른쪽으로 이동 a > > 1 = 0010 b
0
0
1
0
0
0
0
1
이때 b [1] = 0
a 오른쪽으로 이동 a > > 1 = 0001
0
0
0
1
0
0
0
1
b[2] = 1
a 오른쪽으로 이동 a > > 1 = 0000
0
0
0
0
0
0
0
1
b[3] = 0
a 의 변위 끝...이때 우 리 는 1 차원 배열 b [] = {1, 0, 1, 0} 을 얻 었 다.
우 리 는 그것 이 바로 우리 의 a 의 2 진 역순 이라는 것 을 볼 수 있다. 만약 당신 이 역순 을 좋아 하지 않 는 다 면 자신의 방식 으로 정상 적 인 배열 을 얻 을 수 있다.
a 의 변위 키 코드:

private static int[] getBitShift(int a, int n) {
		int[] bit = new int[n];
		for (int i = 0; i < n; ++i) {
			bit[i] = a&1;
			a >>= 1;
		}
		return bit;
	}

전체 AC 코드

import java.util.Scanner;

public class Main {

	private static final int N = 4;

	/**
	 *                 
	 * @param a
	 * @param n
	 * @return
	 */
	private static int[] getBitShift(int a, int n) {
		int[] bit = new int[n];
		for (int i = 0; i < n; ++i) {
			bit[i] = a&1;
			a >>= 1;
		}
		return bit;
	}

	/**
	 *     bit      sum 
	 * @param bit
	 * @param datas
	 * @return
	 */
	private static int getBitShiftSum(int[] bit, int[] datas) {
		int sum = 0;
		for (int i = 0; i < datas.length; i++) {
			if (bit[i] == 1) {
				sum += datas[i];
			}
		}
		return sum;
	}
	
	/**
	 *                   
	 * @param datas
	 * @param t
	 * @return
	 */
	private static int getCount(int[] datas, int t) {
		int count = 0;
		for (int i = 0; i < (1 << datas.length); ++i) {
			int[] bit = getBitShift(i, datas.length);
			if (getBitShiftSum(bit, datas) == t) {
				count++;
			}
		}
		return count;
	}

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		int t = input.nextInt();
		int[] datas = new int[n];
		for (int i = 0; i < n; i++) {
			datas[i] = input.nextInt();
		}
		System.out.println("" + getCount(datas, t));
	}
}

여기 서 또 다른 블 로 그 를 보 여 드 리 겠 습 니 다. '재 귀 와 변위 로 매 거 진 서브 집합' 은 재 귀 와 변위 두 가지 방법 으로 매 거 진 서브 집합 을 하 는 과정 을 소개 합 니 다. 관심 있 는 친 구 는 가 볼 수 있 습 니 다.
연결 을 클릭 하여 보기.