[구름 난이도3] 비타민 주스 (Java)

https://level.goorm.io/exam/51352/%EB%B9%84%ED%83%80%EB%AF%BC-%EC%A3%BC%EC%8A%A4/quiz/1

구름LEVEL

 

A, B, C를 모두한번씩 포함하도록 해야한다. N이 1000이고 반드시 3개 이하의 조합이 정답이 될 것이기 때문에 시도해봤다. 그런데 시간초과가 발생했다.

그래서 AB의 경우 다음 조합으로 A를 더하려고 하면 시도하지 않는 식으로 수정했더니 간신히 통과했다. 정해는 아닌 것 같은데 정해는 무엇일까 궁금하다.

 

	static void dfs(int idx, String bitamin, int cost, int cnt){
		if(bitamin.contains("A") && bitamin.contains("B") && bitamin.contains("C")) {
			answer = Math.min(answer, cost);
			
			return;
		}
		
		if(cnt == 3) {
			return;
		}
		
		for(int i = idx; i < arr.size(); i++){
			if(visited[i]) continue;
			if(bitamin.contains(arr.get(i).bitamin)) continue;
			visited[i] = true;
			dfs(i + 1, bitamin + arr.get(i).bitamin, cost + arr.get(i).cost, cnt + 1);
			visited[i] = false;
		}
	}

 

dfs의 경우 위처럼 구성했다. 만약 A,B,C를 모두 포함한다면 더이상해볼 필요가 없으니 리턴처리해주고 만약 3개의 조합인데도 불구하고 A,B,C를 채우지 못했다면 이것들은 최소값이 될 수 없으므로 제외한다. 비타민의 경우는 그냥 계속 추가해주는 식으로 구현했다. 오히려 ABC만 남기려고 하는게 더 연산이 필요하게 되어 코드가 어려워질 것 같았다.