[dfs, 백트래킹] sw expert academy 2112번 보호 필름 자바 풀이

sw expert academy 2112번 보호 필름 자바(java) 풀이

• 모의 SW 역량 테스트
• sw expert academy 2112번 보호 필름
  
  
  

문제 정리

1. 보호 필름은 얇은 막 D개를 쌓아서 만든다
2. 얇은 막은 동일한 크기를 가진 바 모양의 셀들이 가로방향으로 W개 붙여서 만든다 (두께 D 가로크기 W의 보호필름 완성!)
3. 각 셀들은 특성 A 또는 B를 가진다.
4. 충격은 보호 필름 단면의 세로 방향으로 가해지므로 세로방향의 특성이 중요하다
5. 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과할 수 있다.
6. 약품을 투입해서 가로 방향의 셀들을 모두 하나의 특성으로 변경할 수 있다. (약품 A -> 모두 A로 변경 / 약품 B -> 모두 B로 변경)
7. 약품을 최소로 투입해서 성능검사를 통과하게 만들어라
8. 약품을 투입하지 않고 통과할 수 있는 경우 0을 출력한다.
   
   
   

문제 풀이

처음에는 순열을 모두 구해서 가지치기 하는 식으로 한다고 했는데 계속 시간초과 나와서 헤맸네요 ㅠㅠㅠ
예전에 이런 비슷한 문제를 푼적있는데 백준에서 풀었나?? 기억이 잘 안나네요 돈 관련된 문제였던것 같은데...
아무튼!!! dfs를 이용하여 풀었습니다.

1. 행을 기준으로 탐색하며 뿌린 약의 수를 계속 저장해나갑니다.
2. 각 행마다 약을 안 뿌리거나 A를 뿌리거나, B를 뿌리거나 3가지의 경우가 있을 수 있습니다. 모두 재귀를 통해 탐색합니다.
3. 전체 film 배열을 바꾸는 것이 아니라 약을 뿌릴 부분의 원본을 복사하여 저장해두고 약을 뿌리고, 재귀가 끝나고 나오면 다시 원상복귀 시킵니다.
4. 그렇게 재귀적으로 약을 뿌리고 안뿌리고.. 탐색하다가 마지막 행에 도달하면 성능검사를 합니다.
5. 성능검사는 그냥 열을 탐색하면 됩니다. 다만 저는 가지치기를 추가하였습니다. 모든 열을 정상적으로 탐색했다면 min 값을 갱신해줍니다.
   • 이미 연속된 특성이 K개가 넘은 경우 다음 열을 탐색하러 간다.
   • 더 탐색해도 K이상의 연속된 수가 나올 수 없는 경우 성능검사를 중지한다.
   • 한 열이라도 연속된 수의 길이가 K 이상이 아니면 성능검사를 중지한다.
6. 이 부분이 제일 중요합니다!!!!!!!!!!!!!! 그렇게 성능검사를 만족할때까지 탐색하다가 만족하게되면 min 값이 바뀌게 됩니다. 그래서 그 min 값 보다 약품을 더 많이 뿌리려는 조건은 모두 가지치기로 탐색하지 않습니다.
   
   
   

보호 필름 자바 코드

• 실행시간: 409 ms
• 메모리: 89564kb