[SWEA] 2112. 보호필름

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

SW Expert Academy

 2019년 12월 30일 오늘도 시간안에 두문제 풀기에 성공했습니다만 그렇게 만족스럽지는 않습니다. 이 문제를 1시간 50분 가량 풀었고 다행히 두번째 문제가 쉬워 40분정도에 해결했습니다. 이 문제를 한번에 풀지도 못해서 7~8번 정도의 시도에 풀었습니다. 그 과정에서 코드를 한번 갈아 엎기도 했습니다.

 

 정답률이 30퍼정도 되는 문제입니다. 제 문제셋 중 정답률이 가장 낮은 것 같네요. 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 되는데 이 성능검사를 통과하기 위해 약품으로 특정 라인의 셀들의 특성들을 바꾸어서 이 성능검사를 통과하는 것이 목표입니다. 당연히 약품 투여 횟수를 가장 적게 해야겠죠. 이 문제는 조금이라도 놓치는 것이 있으면 시간초과가 나거나 틀릴 것 입니다. 저도 한참 고생했네요. 시간에 쫓기다 보니 이런 저런 실수를 많이 했습니다. 

 

 dfs + 시뮬레이션 문제입니다. 첫 코드에서는 각 행을 그대로 놔둘 것인지 A약물처리를  할지 B약물처리를 할지 여부를 벡터에 저장해두었다가 모든 셀들의 정보가 결정이 되면 주어진 셀들의 정보를 복사해서 약물 처리를 해보고 테스트를 통과할 수 있는지를 직접 해보는 식으로 했지만 36개까지 맞고 시간초과가 났습니다. 애초에 10개짜리 테스트 케이스로도 2초가 넘는 시간이 나와서 기대는 안했습니다. 이런 방식으로는 답이 없을 것 같아서 방식을 바꿨습니다.

 

 기본적인 dfs + 시뮬레이션으로 푼 것은 동일합니다. 하지만 이번에는 셀들의 정보를 복사해 dup배열에 저장한 후 직접 dup배열에 약물처리를 할 것이라면 약물처리를 한다음 다음 dfs를 호출하게 됩니다. 이번에는 모든 행에 대해 상태가 결정되면 약물 테스트를 해보는 것이 아니라 각 행에 도달하면 테스트를 통과할 수 있는지를 먼저 체크했습니다.