[SWEA] 2112. 보호 필름

▶문제설명

[SWEA] 2112. 보호 필름

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE

▶Hint

---

DFS 문제이다.

아래와 같이 3번의 재귀 호출로 모든 경우를 탐색할 수 있다.

현재 필름의 상태를 저장한다.

1. 약품을 주입하지 않고

다음 필름의 인덱스와 현재 약품 주입 횟수를 인자로 하여 함수를 재귀적으로 호출한다.

2. 현재 필름에 A약품을 주입하고 

다음 필름의 인덱스와 현재 약품 주입 횟수+1을 인자로 하여 함수를 재귀적으로 호출한다.

3. 현재 필름에 B약품을 주입하고

다음 필름의 인덱스와 현재 약품 주입 횟수+1을 인자로 하여 함수를 재귀적으로 호출한다.

현재 필름을 약품 주입 전의 상태로 복구한다.

또한, 재귀함수의 탈출 조건이 중요하다.

[탈출 조건]

1. 현재까지 테스트를 통과한 최소 약품 주입 횟수 이상인 경우 

(현재 약품 주입 횟수 >= answer)

테스트 통과시 약품 주입 횟수와 answer 값을 비교하여 최소값으로 업데이트한다.

2. 필름의 인덱스 범위를 초과하는 경우 

(현재의 필름 인덱스 == D)

▶Solution

마지막 수정 일시 : 2019.04.09. 12:26