문제

근손실

풀이

n : 입력 값의 갯수 n
k : 하루에 근손실 발생양
arr : 하루에 생성되는 근육량
power : 현재 근육량

하루동안의 근육량은 다음과 같습니다.

arr[i] - k

그렇다면 현재 근육량을 구할때는 다음과같습니다

power + arr[i] - k

해당 점화식이 0 미만이되는 순간 근손실이 발생한다고 생각하면 됩니다
그럼 이 근육량이 3일동안 들어오게 되는 경우의 수를 생각 해보면 다음과 같습니다

0, 1, 2
0, 2, 1
1, 0, 2
1, 2, 0
2, 1, 0
2, 0, 1 

이와같이 순서가 다르게 3개씩 고르는 방법을 생각하면 됩니다.
방문 한 후에 선택하지 못하도록 visited 배열을 생성하였습니다

boolean[] visited = new boolean[n];

해당 배열은 한번 선택한 후 다시 선택할 수 없도록하는데, 0 부터 N-1까지 반복해 주어야 합니다. 반복해주어야 할것으로는 앞서서 말했던 점화식을 dfs에 대응해주겠습니다.

for (int i = 0; i < n; i++) {
	if (!visited[i]) {
    	visited[i] = true; // 선택한 후 다시 선택할 수 없게 한다.
		if (power + arr[i] - k >= 0) { // 정수 일때만 dfs가 적용된다. 
        	dfs(depth + 1, power + arr[i] - k); 
        }
		visited[i] = false; // 순서가 다르게 재선택하겠다.
    }
}

종료되어야 할 조건

• n - 1 인경우 종료되어야 합니다. 3개를 골라야 하기 때문입니다.
• power가 0이상인 값으로 종료되어야 합니다.

두개를 동시에 만족하는 것이 근손실이 일어나지 않은 조건에 해당하기 때문에 코드는 다음과 같습니다

private static void dfs(int depth, int power) {
	if (depth == n - 1 && power >= 0) {
    	answer++;
        return;
    }
    
    for (int i = 0 ;i < n; i++) {
    	if (!visited[i]) {
			visited[i] = true;
            if (power + arr[i] - k >= 0) {
            	dfs(depth + 1, power + arr[i] - k);
            }
            visited[i] = false;
        }
    }
}

전체 코드

전체 코드