[알고리즘] 2021 SCPC 후기 (Round 1)

 

---

이번 SCPC ROUND 1은 작년보다 난이도가 확연히 내려갔습니다.

사지방에서 풀이하는 특성 상 긴 시간을 이용하지 못해 SCPC Round1 예선의 정석인 1,2번을 풀이하고

남은 3문제를 부분 테스트케이스 점수를 가져가는 방법을 택하였습니다.

코드도 저장해두었지만, 풀이만 남겨보도록 하겠습니다.
(해당 문제의 정답 풀이가 아닌 부분 테스트 케이스의 정답 풀이도 포함되어 있습니다.)
(SCPC Round 1은 경험 상 1000명정도 통과하는 것 같습니다.)

---

 

문제1. 친구들 [80 / 80]

알고리즘 : 유니온파인드

문제1은 친구들의 관계의 수를 구하는 문제인데 A,B가 친구고 A,C도 친구면 B,C도 친구인 친구관련 알고리즘 문제의 흔한 문제이나, 해당 Di의 수 만큼의 옆인 친구와 관계인 단방향인 관계라 유니온파인드가 아닌 DFS로도 풀이할 수 있습니다.

그러나, 유니온 파인드로 풀이 시, 더 깔끔할 것 같아 이를 이용해 풀이하였습니다.

 

---

 

문제2. 이진수 [150 / 150]

알고리즘 : 그리디

비트를 처음 입력받을 때 문자열로 받은 뒤 비트문제 특성 상 처음 입력받은 비트가 최상위 비트이므로 문자열을 리버스 해주었습니다.

하위 비트부터 읽으면서 해당 번째에 넣을 수 있는 비트 (i+k, i-k)가 있는지 확인해 주고, 상위비트에서 부터 내려오면서

 

만약 이 비트를 사용해서 두개를 해결할 수 있다면 사용 -> 사용, 겹치는 곳의 다른 비트는 버림

하나에 밖에 사용 못하는데 해당 비트를 사용하는게 현재 비트 뿐이다 -> 사용

하나에 밖에 사용 못하는데 해당 비트를 사용하는게 두개 이상 비트다 (즉, 더 작은 비트가 그 비트를 채워줄 수 있다.) -> 버림

 

으로 진행하였습니다.

예외가 하나 있었는데, 2번 예시에서 해당 비트를 사용하고자 할 때 답을 포함하는 011110000이 나와야하는데 0011110000이

나오면서 답을 포함하는 더 큰 비트의 답이 나왔습니다. 처음에 낮은 비트에서부터 추가를 할 때, 해당 비트가 관여하는 i+k, i-k가

둘 다 1인 순번만 추가하는 식으로 해결하였습니다.

 

---

 

문제3. No Cylce [41 / 180]

알고리즘 : 비트마스크

처음엔 휴리스틱 기법인 시뮬레이티드 어닐링을 사용하여 풀이하려고 했는데 나올 수 있는 값 중 가장 작은 비트인 결과 값을

출력하라는 문제 요구사항을 보지 못하고 8회를 제출하게 됩니다. 그래서 휴리스틱 기법 특성 상 2번 안에 정해가 나온다는 걸

보장할 수 없기 때문에 N이 10인 부분 테스트케이스 1의 경우에 확실히 답이 나올 수 있는 비트마스크를 활용해

모두 정방향인 0000000000 ~ 모두 역방향인 1111111111(2^10 - 1)까지 '모두' 순회하면서 결과값을 갱신했습니다.

위에서 말했던 가장 작은 비트를 출력해야하는 문제라 모두 순회하였고, 역방향으로 출력하는 문제인 만큼 2번비트를 역으로

출력하는 01000 보다 5번비트를 역으로 출력하는 00001 이 더 작기 때문에 이렇게 진행하여 부분 테스트 케이스 1을 땄습니다.

 

---

문제4. 예약 시스템 [37 / 190]

알고리즘 : 구현

각 그룹의 예약자 수인 L[i]가 짝수, 홀수만 존재하는 테스트케이스를 노리고 풀이하였습니다. L[i]가 짝수라면 양 사이드에 있는

그룹은 스트레스가 가장 낮은 두명이 스트레스를, 중간에 있는 그룹은 최저 4명이 스트레스를 받게 됩니다.

그렇기 때문에 이중 포문으로 i,j번째 그룹의 최저 2명의 스트레스를 나머지 그룹의 4명 스트레스 값을 더해 나온 결과값의 최저를 갱신해 풀이하였습니다.

(코드에서는 전체 최저 4명 스트레스 값에서 두 그룹의 4명 스트레스 값을 빼고 2명 스트레스 값을 더하면 시간이 절약됩니다.)

N이 20000이라서 단순 i*j로는 시간제한 3초를 초과할 수 있기 때문에 j의 범위를 (i+1 ~ N)으로 지정해주었습니다.

문제를 제대로 이해하지 못해 홀수인 부분도 이렇게 풀이 될거라 생각했지만 홀수인 부분은 두 면이 닿는다는 것을 고려하지 못하고 시간 상 넘어갔습니다.

 

---

 

문제5. 차이 [51 / 200]

알고리즘 : 유니온 파인드

부분 테스트 케이스를 보자마자 유니온 파인드라고 떠올랐던 문제입니다. 1,3번 케이스가 두 변수의 차이가 0임으로 다른 것을

고려 할 사항이 없어 시간복잡도가 최적화된 유니온 파인드로 다른 문제보다 쉽게 점수를 따올 수 있었습니다.

부분 테스트 케이스 점수가 있는 대회들은 정답을 못 푼 문제들의 부분 점수 합만 합쳐도 다른 문제의 1문제이상의 점수가 될 수 있기 때문에 SCPC Round1에서는 주어진 시간이 많았지만, 짧은 시간내에 부분 점수를 따는 방법을 공부하는 것도 중요한 것 같습니다.

 

---

2021.07.24

1차 통과했습니다.

 

< 2차 예선 후기 보기 >

https://mumomu.tistory.com/56

[알고리즘] 2021 SCPC 후기 (Round 2)

---

#2021 SCPC #2021 SCPC round1 #2021 SCPC 1차예선 후기 #SCPC 1차예선 후기 #SCPC round1 후기 #2021 SCPC 후기

#SCPC 친구들 #SCPC 이진수 #SCPC nocycle #SCPC 예약시스템 #SCPC 차이 #2021 scpc 풀이 #2021 scpc 합격컷

#scpc 1차 풀이 #scpc 1차 후기 #scpc 1차 합격컷 #codeground