SUAPC 2020 div2 후기

https://www.acmicpc.net/category/detail/2275

신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 (SUAPC 2020) Div. 2

 

A,B : div2는 A,B가 무조건 쉬운 문제로 구성이 되어 있다고 해서, 나는 반대로 A,B는 문제를 읽어보지도 않았다. 이번년도에 입학한 신입생분과 알고리즘 시작한지 얼마 안되신 분이 풀도록 ... 

 

사실 문제를 읽어본 문제들이 D,G,K,L이라서 

 

이것들에 대해서만 얘기해보려고 한다.

 

D. 비드맨

 

너무 쉬웠다. 

 

여러 종류의 구슬이 있을때에, 다른 종류의 구슬끼리 부딪혀서 파괴할 수 있다. 

이때에 가장 많이 부딪혀서 구슬을 없앤다고 하면 남은 가장 적은 갯수의 구슬은 몇개일까

 

일단 구슬을 가장 큰 갯수를 갖고있는 구슬을 없애야 한다고 생각했다. 

 

왜냐 그렇지 않으면 결국 작은 놈들끼리 싸우고, 큰놈만 득을 보게 된다. 그래서 pq로 뚝딱하고 제출했으나 WA

 

... 

 

이유를 몰랐다. 반례도 전혀 찾지 못 했고, 그래서 다음 문제로 패스 

 

G. 약수 

 

나무들이 있는데 길이가 주어지고, 그 나무들이 서로 큰 수에서 작은 수를 나눴을때 나누어 떨어지게 만드려면 최소 몇 개의 나무의 길이를 변경해야 하는지에 대한 문제

 

음 일단 서로 나누어 떨어지게 하려면 가장 작은 수의 배수들로 나무가 이루어져야 한다고 생각을 하였다. 

 

그래서 일단 정렬을 한 뒤에 가장 작은 나무부터 뒤에 나누어 떨어지지 않는 경우를 세보았다. 

 

그렇게 해서 N^2번 하면 될것같아서 대강 구현했지만 WA후 반례를 몇 개 찾은 것 같아서 패스 

 

K. 객실 배치 

 

dp같았다. 그래서 해당 층 방에 사람이 있을 때, 없을 때에 조건을 나누어서 dp[층][포함여부] 로 풀면 되겠다 싶었지만

 

N이 10^8보다 커서 선형 dp로 하면 시간초과 난다는 사실을 알고,

 

다른 풀이를 생각, 반으로 쪼개도 풀 수 있겠다 싶었지만 구현이 어려울 것 같아서 패스... 

 

L. 200년간 폐관수련했더니 PS 최강자가 된 건건에 대하여

 

이 문제를 볼때는 30분정도 남아있었는데, 문제가 쉬워보였다. 그냥 한번까지는 봐준다는 소리였고, 그 한번이 언제가 될지 결정을 해야 되는 문제였다. 

 

그래서 후딱 구현하고, 제출했지만 WA..

 

대회를 통과 못 할때를 패스할건지 그 전에 최대상금을 포기해서 그 대회를 참석할건지를 결정하면 된다. 그래서 그 조건을 추가하였고, 제출하였으나 또 WA.. 그래서 마지막으로 검토하던중에 KKe - ok이런식으로 제출해야 하는 문자에 띄어쓰기가 있다는 사실을 발견하고, 수정해서 제출했더니 성공 ,,, 

 

 

겨우 1솔을 했다. 

 

사실 D번은 자면서 생각을 해봤는데, 일단 내가 생각한 방법의 문제점은 6 5 2 같은 경우였다. 

 

6 6 5 5 2 는 큰것부터 없애게 된다면 2가 남고, 따로 제거를 하면 0이 남는 상황이었다. 그래서 계속해서 이 것을 어떻게 구현해야 됬을까 생각을 해봤는데.. 방법을 못 찾아서 풀이를 봤는데 ... 

 

문제를 어디선가 잘못 이해했다. 나는 구슬을 부딪힐때에 그 종류의 모든 구슬을 부딪힌다고 생각을 하고 풀었었고 그렇게 푼다면 구현이 부딪힐때마다 조건을 따졌어야 했을것이다. 

 

그냥 홀짝으로 나누면 되는 문제였는데 이런게 아쉽다. 

 

약수는 아직 안 풀어봐서 다시 생각을 해봐야 겠다. 

 

부족한 점이 많고, 이런 대회하고 친구만나고 오면 꼭 의지도 리셋이 된다. 열심히좀하자 제발 .. 

 

잘하자