2020 SCPC 1차 예선 통과

 

이번에 SCPC Round 1을 통과하였다. 목표는 본선이지만 아직 실력의 부족함을 많이 느끼는 중이였는데 2번부터 막혀서 설마 1라운드도 통과 못하는 거 아닐까 생각이 들었지만 276점으로 다행히 통과를 하였다.

1번 문제는 정렬만 하면 만점인 문제였다.

2번부터 갑자기 난이도가 많이 올라갔다. 어려워하는 dp 문제여서 고민을 많이 하다가 탑 다운으로 N^2으로 풀었는데도 TLE가 나서 당황을 많이 했지만 겨우겨우 현재 좌표까지의 상태를 저장하는 구간합과 바텀 업 dp를 사용하여 같은 N^2으로 만점을 받았다. 제한 시간을 빡빡하게 줘서 탑 다운으로 하면 함수 오버헤드가 나서 TLE이 났던거 같다.

3번은 우리가 잘 아는 사다리 게임에서 (i , j)로 갈 수 있도록 파괴한 가로선의 최솟값들을 구하는 문제였다. 2번에서 시간을 많이 써서 일단 dfs로 26점을 챙기고 더 생각이 안났다. 끝난 후 dp나 bfs를 이용하여 풀 수 있다는 소리를 들었고 bfs로 다시 풀어보았다.