#2112. [모의 SW 역량테스트] 보호 필름

출처:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

SW Expert Academy

 

풀이

dfs를 이용한 구현문제이다. 문제에서 구현해야하는 핵심은 투여해야할 배양액을 조합을 통해 선정해야 한다.

예를들어 두께가 4이고 합격기준이 2라고 하면 4개에서 2개 이하를 뽑는 조합은 다음과 같다.

0000 1000 1100 1010 1001 0100 0110 0101 0010 0011 0001 

하지만 1인 부분에 배양액 a와 b로도 또 구분할 수 있으므로 다음과 같이 배열을 만들어야 한다.

0000: 

1000: 1000 2000

1100: 1100 1200 2100 2200

1010: 1010 1020 2010 2020

1001: ...

0100:

0110:

0101:

0010:

0011:

0001: 0001 0002

 

이렇게 배열을 뽑고 나서 보호필름이 연속적으로 합격기준 k를 만족시키는지만 뽑아주면 된다. 따라서 사실상 배열 조합식을 어떻게 짜느냐가 핵심이라고 할 수 있다.

 

그리고 재귀 함수에서 시간을 줄이는 핵심이 있다. 앞서 구한 최솟값이 현재 카운트 값보다 크거나 같으면 더이상 진행할 필요 없으므로 리턴을 시켜주는 코드를 한 줄 넣게되면 시간이 많이 줄어들게 된다. 

 

코드