[SWEA] 2112. 보호필름
문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
2019년 12월 30일 오늘도 시간안에 두문제 풀기에 성공했습니다만 그렇게 만족스럽지는 않습니다. 이 문제를 1시간 50분 가량 풀었고 다행히 두번째 문제가 쉬워 40분정도에 해결했습니다. 이 문제를 한번에 풀지도 못해서 7~8번 정도의 시도에 풀었습니다. 그 과정에서 코드를 한번 갈아 엎기도 했습니다.
정답률이 30퍼정도 되는 문제입니다. 제 문제셋 중 정답률이 가장 낮은 것 같네요. 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 되는데 이 성능검사를 통과하기 위해 약품으로 특정 라인의 셀들의 특성들을 바꾸어서 이 성능검사를 통과하는 것이 목표입니다. 당연히 약품 투여 횟수를 가장 적게 해야겠죠. 이 문제는 조금이라도 놓치는 것이 있으면 시간초과가 나거나 틀릴 것 입니다. 저도 한참 고생했네요. 시간에 쫓기다 보니 이런 저런 실수를 많이 했습니다.
dfs + 시뮬레이션 문제입니다. 첫 코드에서는 각 행을 그대로 놔둘 것인지 A약물처리를 할지 B약물처리를 할지 여부를 벡터에 저장해두었다가 모든 셀들의 정보가 결정이 되면 주어진 셀들의 정보를 복사해서 약물 처리를 해보고 테스트를 통과할 수 있는지를 직접 해보는 식으로 했지만 36개까지 맞고 시간초과가 났습니다. 애초에 10개짜리 테스트 케이스로도 2초가 넘는 시간이 나와서 기대는 안했습니다. 이런 방식으로는 답이 없을 것 같아서 방식을 바꿨습니다.
기본적인 dfs + 시뮬레이션으로 푼 것은 동일합니다. 하지만 이번에는 셀들의 정보를 복사해 dup배열에 저장한 후 직접 dup배열에 약물처리를 할 것이라면 약물처리를 한다음 다음 dfs를 호출하게 됩니다. 이번에는 모든 행에 대해 상태가 결정되면 약물 테스트를 해보는 것이 아니라 각 행에 도달하면 테스트를 통과할 수 있는지를 먼저 체크했습니다.
| #include<iostream> | |
| #include<vector> | |
| #include<algorithm> | |
| using namespace std; | |
| int d, w, k, tc, ans; | |
| int map[13][20]; | |
| int dup[13][20]; | |
| bool test() | |
| { | |
| for (int i = 0; i < w; i++) | |
| { | |
| bool check; | |
| for (int j = 0; j <= d - k; j++) | |
| { | |
| int a = dup[j][i]; | |
| check = true; | |
| for (int p = 0; p < k; p++) | |
| { | |
| if (dup[j + p][i] != a) | |
| { | |
| check = false; | |
| break; | |
| } | |
| } | |
| if (check) | |
| break; | |
| } | |
| if (!check) | |
| return false; | |
| } | |
| return true; | |
| } | |
| //약물검사 테스트 | |
| void medicine(int idx, int m) | |
| { | |
| for (int i = 0; i < w; i++) | |
| { | |
| dup[idx][i] = m; | |
| } | |
| } | |
| //약물처리 | |
| void restore(int idx) | |
| { | |
| for (int i = 0; i < w; i++) | |
| { | |
| dup[idx][i] = map[idx][i]; | |
| } | |
| } | |
| //복구 | |
| void dfs(int k, int cnt) | |
| { | |
| if (test()) | |
| ans = cnt < ans ? cnt : ans; | |
| if (k == d) | |
| return; | |
| if (cnt >= ans) | |
| return; | |
| //현재의 cnt가 현재까지의 ans보다 크면 더 탐색할 필요가 없다 | |
| for (int i = 0; i < 3; i++) | |
| { | |
| if (i != 0) | |
| { | |
| medicine(k, i - 1); | |
| dfs(k + 1, cnt + 1); | |
| restore(k); | |
| } | |
| //약물처리를 하는 경우 | |
| else | |
| { | |
| dfs(k + 1, cnt); | |
| } | |
| //약물처리를 하지 않는 경우 | |
| } | |
| } | |
| int main(void) | |
| { | |
| ios::sync_with_stdio(false); cin.tie(NULL); | |
| cin >> tc; | |
| for (int t = 1; t <= tc; t++) | |
| { | |
| cin >> d >> w >> k; | |
| ans = 10000; | |
| for (int i = 0; i < d; i++) | |
| { | |
| for (int j = 0; j < w; j++) | |
| { | |
| cin >> map[i][j]; | |
| dup[i][j] = map[i][j]; | |
| } | |
| } | |
| dfs(0, 0); | |
| cout <<'#'<<t<<' '<< ans << '\n'; | |
| } | |
| } |