https://www.acmicpc.net/problem/18429
18429번: 근손실
웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로
www.acmicpc.net
코드설명
백트래킹(Backtracking) + DFS(깊이우선탐색) + 일반순열(Normal Permutation) 을 활용하는 문제입니다.
- simulate 재귀함수를 통해 완전탐색 및 순열을 만들어서 진행합니다.
- sum은 현재까지 선택한 원소들의 합을 나타냅니다. 선택한 원소의 값에서 K를 뺀 값이 500 이상인 경우에만 다음 레벨로 넘어가고, 그렇지 않은 경우에는 해당 원소를 선택하지 않은 상태로 다음 레벨로 넘아갑니다.
- 재귀 호출을 통해 가능한 모든 경우의 수를 탐색하며, 조건을 만족하는 경우 answer를 증가시킵니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K ;
public static int answer = 0;
public static int[] arr;
public 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());
arr = new int[N];
visited = new boolean[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
simulate(0, 500);
System.out.println(answer);
}
public static void simulate(int level, int sum) {
if(level == N) {
// System.out.println("level:"+level+"sum:"+sum);
answer += 1;
return ;
}
for(int i=0;i<N;i++) {
if(visited[i] == false) {
visited[i] = true;
if( sum + arr[i] - K >= 500 )
simulate(level + 1, sum + arr[i] - K);
visited[i] = false;
}
}
}
}