기다리던 SCPC 1차 예선이 있었습니다.
총 5문제 중 3문제를 풀었고, 나머지 2문제는 조금의 부분점수를 받았습니다.
갈 길이 멀지만 그래도 실력에 비해 점수를 잘 받은 것 같아 기분은 좋습니다.
1번 [개미] 100/100
위치와 값을 묶어서 정렬만 하면 해결되는 간단한 문제였습니다.
2번 [K등분] 10/140
처음에는 DFS로 돌려보았는데, 시간초과로 부분점수 10점을 받았습니다.
접근방법이 잘못된 것 같아 나름대로 고민하여 새롭게 짜보았는데 오히려 0점이 나왔습니다.
그렇게 어렵지 않아보였는데 어느새 제출 횟수 10번을 넘겨서 결국 10점으로 마무리했습니다.
(2023-01-08 수정)
페르마소정리로 모듈러 곱셈 역원을 구하여 이항계수를 빠르게 구하는 방법을 알아야 해결가능한 문제였습니다.
3번 [직교 다각형] 140/140
점의 총 개수가 홀수일 때에만 에러점이 발생하고, 에러점이 있으면 해당 행과 열은 점의 개수가 홀수가 됩니다.
에러점을 찾았으면 에러점을 없애고 다각형을 만들어 주면 되는데 그냥 2개씩 짝지어 이어주었습니다.
4번 [지우개] 190/190
찾는 문자열의 구조에 따라 3가지로 나누었습니다.
1. a나 b 한문자로만 구성된 경우
2. a와 b가 서로 분리되어 뭉쳐있는 경우
3. a, b가 골고루 섞여있는 경우
세번째 경우에서 처음에는 그냥 중간 영역을 string::find로만 확인을 했는데 시간 초과로 95점이 나왔고, KMP를 적용하고나서야 점수를 모두 받을 수 있었습니다.
5번 [독립] 12/230
어떻게 풀어야 할지 막막해서 우선 BFS를 통해 탐색을 하며 각 지점에 도달할 수 있는 점들을 set으로 저장해두었고, 그 데이터로 각 지점에서의 ‘독립’ 으로 판별되는 쌍들을 계산했습니다.
역시 예상대로 시간초과가 나왔으나 부분점수 12점은 받았습니다.
떨어지더라도 공부는 계속하겠지만, 점수를 보면 2차 진출이 가능해보입니다.
