[백준] JAVA - 18429.근손실

생각

운동키트의 중량이 같다고 하더라도 이를 모두 다르게 보기 때문에 모든 경우의 수를 탐색해야하는 순열로 생각하여 풀었습니다. 가능한 경우를 생성하고 이때 N일동안 근육량이 500이상이 되는지 체크한뒤 가능한 경우의 수를 카운트하였습니다.

 

이번 문제에서는 순열을 비트마스킹을 통해 생성했습니다.

permutation함수에서 cnt는 현재까지 뽑은 순열 원소의 개수를 의미하고 flag 는 선택한 원소의 비트정보를 나타냅니다. 이때 flag를 통해 선택한 원소인지를 판단할 수 있습니다.

 

N개를 나열한다고 했을때 i번째가 선택됐는지 아닌지를 비트연산인 (flag & 1<<i) 를 통해 체크합니다.

i번째 비트가 0이 아니라면(사용되지않았다면) cnt를 1증가시키고 (flag | 1<<i) 비트 연산을 통해 i번째 비트를 1로 마스킹처리한뒤 다음 자리에 올 숫자를 뽑으러 한 단계 들어갑니다.

 

 

Java code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baekjoon_18429_근손실 {
/**
 * 운동키트 순열로 N일동안 근육량 500이상이 되도록하는 경우의수 찾기
 * 운동키트 모두 다름 -> 순열
 * 하루지날때 근육량 K만큼 감소
 * @throws IOException 
 * */
	static int N;
	static int K;
	static int[] arr;
	static int[] result;
	static int ans;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] init = br.readLine().split(" ");
		N = Integer.parseInt(init[0]);
		K = Integer.parseInt(init[1]);
		arr = new int[N];
		result = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		ans = 0;
		//순열 생성
		permutation(0, 0);
		System.out.println(ans);
	}
	
	private static void permutation(int cnt, int flag) {
		if(cnt == N) {
			//매일 500이상 중량 되는지 체크
			if(check(result)) ans++;
			return;
		}
		for (int i = 0; i < N; i++) {
			if((flag & 1 << i) != 0) continue;
			result[cnt] = arr[i];
			permutation(cnt+1, flag | 1 << i);
		}
	}
	
	private static boolean check(int result[]) {
		int weight = 500;
		for (int i = 0; i < N; i++) {
			weight -= K;
			weight += result[i];
			if(weight < 500) return false;
		}
		return true;
	}

}