백준_18429 근손실(자바)/ 백트래킹

시간&메모리 제한

 

문제

 

입력&출력

 

문제 풀이

package com.Back;

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

public class Back_18429 {
	static int N,K,ans;
	static int weight[];
	static boolean visited[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		weight = new int[N];
		visited= new boolean[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			weight[i]=Integer.parseInt(st.nextToken());
		}
		perm(0,0);
		System.out.println(ans);
	}

	private static void perm(int cnt,int totalweight) {
		if(totalweight<0)return;
		if(cnt==N) {
			ans++;
			return;
		}
		for (int i = 0; i < N; i++) {
			if(visited[i])continue;
			visited[i]=true;
			perm(cnt+1, totalweight+weight[i]-K);
			visited[i]=false;
		}
	}
}

- 이 문제는 브루드 포스랑 백트래킹을 이용하는 문제입니다.

- 순열을 이용해서 N개 중에 N개를 나열 하는데 순서가 존재합니다.

- 각 단계에서 500이하로 내려가면 안되기 때문에 메소드 시작하는 부분에서 예외처리를 해줍니다.

- 현재 cnt 및 전체 무게를 계속 카운팅 해주면서 진행하면 됩니다.