2024 SCPC (삼성 대학생 프로그래밍 경진대회) 1차 예선 후기
1. A보다 B가 좋아 (예측 S3) #문자열 #애드혹모든 AA와 ABA를 지워주기 위해 사이에 B를 끼워넣어주면 된다. 증명: 어떤 구간 [l, r] 사이에 있는 A가 B보다 많다고 하자. 주장은 이 안에 적어도 1개의 AB 또는 ABA가 있다는 것이다. 이를 검증하기 위해 귀류법으로 저런 패턴이 없다고 가정하고, ABBABBA... 이렇게 써 보면 절대 A가 B보다 많아지지 않는다. 2. 배달 (예측 S1) #정렬 #애드혹 #그리디문제에서 주어진 식, |a-b|+|b-c|+|c-d|+|d-a|는 2*max(a,b,c,d) - 2*min(a,b,c,d)와 같다. 따라서 정렬 후 a, d를 가장 바깥쪽에서 골라주고 b, c를 가장 안쪽에서 골라주면 된다. 이를 N/4번 반복. 3. 보안망 점검 (예측 ..
2024. 7. 6.
