[백준 JAVA] 18429번: 근손실

https://www.acmicpc.net/problem/18429

 

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

public class Main {
	public static int N, K, ans = 0;
	public static int[] A, arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 1. 입력 받기
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		A = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		// 2.조합 짜기
		dfs(0, new int[N], 500);

		// 3. 출력하기
		System.out.println(ans);
	}

	public static void dfs(int depth, int[] visited, int weight) {
		if (depth == N) {
			ans++;
			return;
		}
		for (int i = 0; i < N; i++) {
			if (visited[i] == 0) {
				visited[i] = 1;
				int cur = weight + A[i] - K;
				if(cur >= 500) {
					dfs(depth+1, visited, cur);
				}
				visited[i] = 0;
			}
		}
	}
}

 

## 풀이 사항
풀이 일자: 2024.10.25
풀이 시간: 20분
채점 결과: 정답
예상 문제 유형: 순열, 백트래킹
시간: 116 ms
메모리: 14204 kb

## 풀이방법
두가지 풀이방법을 이용해서 풀이해봤다.
1. 운동 키트 사용 순서를 순열을 이용해서 끝까지 구한 다음에 운동하고 500이하로 내려가면 바로 리턴, 끝까지 500이하로 내려간적이 없다면 정답 증가
2. 똑같이 dfs 순열을 이용하긴 하지만, 운동 키트 순서를 정할때 마다 계산해서 500이하로 내려간다면 다음 dfs로 들어가지 않게 해주었다. 500이하로 내려가지 않는다면 파라미터로 현재 weight값을 넘겨주어 재귀해주었다.
3. 시간차이가 많이 날꺼라 기대했지만 똑같았다. visited방문 배열을 언제 초기화 해주어야 하는지 아직도 햇갈린다.