solved.ac Grand Arena #2 참가 후기

 

 

※ 이 글은 대회가 종료되고 놀다 온 이후에 작성자의 기억을 바탕으로 작성된 글로,

    그때의 감상 및 시점을 기준으로 작성되었음을 미리 알려드립니다.

 

 

 

* 대회 링크

 

https://www.acmicpc.net/contest/view/1077

solved.ac Grand Arena #2 · Arena #2

 

 

 

 

대회가 끝나고 한 일주일 풀로 놀았다

 

개강 싫어 흑흑

 

A, B, C, F 를 풀었고, I는 시도하다가 실패했다.

 

 

 

 

A. 세제곱의 합 (해결)

 

저번 아레나 A번과 같이 기본적인 구현 문제다.

 

범위가 int를 넘어가지 않기 때문에 보이는대로 풀면 된다.

 

 

 

 

B. FizzBuzz (해결)

 

FizzBuzz 관련 문제가 이미 다른 것이 있긴 하지만,

 

그걸 이용한 또다른 배수 관련 문제인데,

 

반드시 세 개의 문자열 중 하나에는 수가 들어올 수밖에 없다는 것을 이용하면

 

그 수를 기준으로 세 개의 문자열 다음에 뭐가 올지를 알 수 있다.

 

 

 

 

C. Double It (해결)

 

집합 내 두 수를 선택해서 가장 큰 두 수의 차가 최소가 되도록 하는 문제인데,

 

처음에는 최대한 기존 최소~최대값에 가까운 수가 되도록 곱해주는 방식으로 생각했는데,

 

반례 케이스(오히려 곱해서 수가 그 범위를 넘어갈 때 최솟값이 나오는 경우가 있었음)를 찾아서

 

가장 작은 수를 계속 꺼낼 수 있도록

 

priority queue를 이용해서 최솟값이 1,000,000,000를 넘을 때까지

 

(이 경우가 나오려면 모든 값에 2 이상이 곱해져야하며, 이에 따라 최댓값과 최솟값의 차이가 최소가 될 수 없다)

 

계속 pop을 하면서 2를 곱해주고 넣어주며 계속 차의 최솟값을 구해주는 방식으로 해결했다.

 

 

 

 

 

F. 럭키 세븐 (해결)

 

결국에는 7의 배수가 되도록 하기 위함이기 때문에,

 

굳이 나올 수 있는 모든 값의 범위를 기준으로 메모리를 구성할 필요없이,

 

7로 나눈 나머지를 기준으로 N(200,000) * 7 크기의 배열을 메모리로 사용하여

 

Dynamic Programming으로 1과 0으로 구분하여 7의 배수가 될 수 있는지 구하면 된다.

 

 

 

 

 

I. 와일드카드 괄호 문자열 (미해결)

 

일반적인 괄호 문제는 'stack'을 이용한 것이

 

가장 기본적인 해결방법으로 사용되기 때문에 이를 이용해서 풀려고 시도했다.

 

케이스를 필요한만큼 구분하여 '?'나 '*' 에 대해서 잘 작동하도록 했지만,

 

개인 테스트케이스는 넘어갔지만 제출 시에 실패가 떴고

 

결국 반례를 시간 내에 찾지 못하여 해결하지 못하였다.

 

 

 

 

 

총평 및 여담

 

I가 또 아깝다.

 

저번에도 한 문제 더 풀 수 있을 것 같았는데

 

또 4문제 풀고 하나 더 해보려다 실패했다.

 

퍼포먼스는 저번과 비슷한 SS+이 떴고,

 

레이팅은 B+에서 A+로 올라갔다.

 

 

레이팅 인정되는 대회가 그 뒤로 여럿 있긴 했지만,

 

본가에 가서 쉬기도 했고,

 

시간대도 저녁 먹는 시간 등 매우 애매해서

 

일단은 더 참가하지는 않았다.

 

재미는 있네