solved.ac 티어 매긴 문제들 - Gold 편

Baekjoon Online Judge에는 유용한 문제 난이도 기능 solved.ac 가 있다.

내가 기여한 문제들의 풀이를 간략하게 써보려고 한다.

 

아마 Gold, Platinum이 주류가 될 것 같고, Diamond 이상은 개별 풀이 포스팅을 할 것 같다.

형식은 문제 번호 (내가 준 티어) 순이다. Gold / Platinum / Diamond 수준의 구분은 신경을 쓰지만, Gold I ~ V의 세부적인 분류는 문제를 푼 직후에 즉흥적으로 내린 경우가 더 많다. 참고 정도만 하자!

 

BOJ 1762. 평면그래프와 삼각형 (Gold II)

불러오는 중입니다...

BOJ 2026. 소풍 (Gold III)

 

Last update 19.12.16.

 

Maximal clique problem의 결정 문제 버전이라서 너무 무섭게 생겼다. 현실은 그냥 백트래킹 돌리면 된다... 복잡도가 보장되지는 않는 것 같다.

 

 

 

BOJ 2132. 나무 위의 벌레 (Gold III)

 

Last update : 2019. 12. 08.

 

트리의 지름 중 시작점 번호가 가장 작은 것을 구하는 문제이다. 트리의 지름을 \(O(n)\)에 구하는 방법은 https://blog.myungwoo.kr/112 에 나와 있는데, 시작점 번호가 가장 작은 지름을 어떻게 특정할 수 있을까?

위의 증명을 알고 있다면 어렵지 않다. x에서 거리가 가장 먼 점을 찾는 과정에서 거리가 같은 점 중에서 번호가 가장 작은 점들을 골라주면 그렇게 고른 지름은 모든 지름들 중에서도 시작점 번호가 가장 작다는 것을 증명할 수 있다.

 

 

BOJ 2423. 전구를 켜라 (Gold II)

 

Last update : 2019. 12. 08.

 

전선들을 connected component처럼 생각하면 접근이 어렵다.

전구와 전원 사이에 가능한 모든 경로를 생각하고, 어떤 경로 P의 비용을 (P가 실제로 이어지기 위해서 돌려야 하는 전선의 수) 로 정의하고 0-1 BFS나 dijkstra를 돌리면 된다. 난 pq쓰기 싫어서 0-1 BFS 썼다. ㅋㅋ!

 

0-1 BFS를 강제했다면 '뇌'를 조금 써야 하니 티어를 좀 더 올렸겠지만, grid 크기가 500 * 500이라서 다익스트라로 충분할 것 같고, 솔직히 0-1 BFS와 다익스트라가 얼마나 practical한 차이가 있는지도 모르겠다.

 

'ㄹ' 형태의 경로가 최적이 되는 경우가 있으므로 구현에 주의해야 한다. 4가지 대각선 방향을 모두 고려하자!

 

BOJ 5485. 평균값 수열 (Gold I)

 

Last update : 2019. 12. 08.

풀이 : https://tamref.com/13

저 문제를 풀 때는 메모리 제한이 16MB였지만, 요즘 누가 그런 메모리 최적화를 하냐는 의미에서(...) 삭제되었다. 실제로 IOI syllabus에서도 빠졌다고 들었다.

 

BOJ 10563. 정수 게임 (Gold II)

 

Last update : 2019.12.16.

 

가장 단순한 형태의 구간 boolean dp로 해결할 수 있다.

현재 남아있는 구간 중 1을 포함하는 구간이 [s,e]라고 하면, 플레이어가 취할 수 있는 행동은 다음과 같다.

 

• [s,e]에 속한 수 하나를 제거한다.
• [s,e]에 속하지 않은 수 하나를 제거한다 - 턴을 하나 넘긴다는 뜻과 동치.

이 행동을 고려하면 [s,e] 구간과, [s,e]에 속하지 않은 수가 홀수 개 있는지 / 짝수 개 있는지 여부만 중요하다는 사실을 알 수 있다. 적절한 dp식을 세우면 해결. 상태가 \(O(n^{2})\)개고 상태별로 \(O(n)\)개의 노드를 참조하기 때문에 \(O(n^{3})\)의 시간복잡도를 갖는다.

 

 

BOJ 10736. XOR 삼형제 2 (Gold III)

10736번: XOR삼형제 2

BOJ 11563. 연돌이와 고잠녀 (Gold I)

 

Last update : 2019.12.16.

 

\(n, m \le 2,000\)이므로, \(nm\)개의 선분 pair에 대해 거리를 전부 구해도 충분하다.

선분과 선분 사이의 최단거리는 구글링을 하거나, 내적을 이용해서 열심히 예외처리를 하면 된다. 오차 제한이 빡빡하지 않기 때문에 이상한 짓만 안하면 통과된다.

 

 

 

BOJ 12911. 좋아하는 배열 (Gold III)

 

Last update : 2019.12.16.

 

 

별로 재미없는 정수론 + DP 문제다.

\(d(n,k)\)를 조건을 만족하는 길이가 \(n\)이고, 마지막 수가 \(k\)인 배열의 개수라고 하자.

\(S(n) = d(n,1) + \cdots + d(n,K)\)를 정의하면 \(d(n+1,k) = S(n) - \sum_{j | k}d(n,j)\)의 relation이 성립한다.

\(1\dots k\)의 수들 중 약배수 관계에 있는 두 수는 \(O(k\log k)\)개 이므로, 전체 문제를 \(O(NK \log K)\)에 풀 수 있다.

 

 

BOJ 13723. 팩토리얼 분수 방정식 (Gold IV)

 

Last update : 2019.12.16

 

주어진 식을 변형하면 \(XY-(N!)(X+Y) + (N!)^2 = (N!)^2 \implies (X-N!)(Y-N!) = (N!)^2\)를 얻는다. \(X,Y > N!\)이어야 하므로 solution의 개수는 \((N!)^{2}\)의 약수의 개수와 같다.

\(N\) 이하의 소수 \(p\)에 대해서 \(p^{k} | N!\)인 maximal \(k\)는 \(N\)의 \(p\)진법 자릿수 합과 같다.

$$ k = \left\lfloor \frac{N}{p} \right\rfloor + \left\lfloor \frac{N}{p^2} \right\rfloor + \cdots $$

답이 \(10^{1017}\)까지 커지는 경우가 있어서 Bigint나 python을 써야 한다.

 

 

주어진 식을 변형하면 \(XY-(N!)(X+Y) + (N!)^2 = (N!)^2 \implies (X-N!)(Y-N!) = (N!)^2\)를 얻는다. \(X,Y > N!\)이어야 하므로 solution의 개수는 \((N!)^{2}\)의 약수의 개수와 같다.

\(N\) 이하의 소수 \(p\)에 대해서 \(p^{k} | N!\)인 maximal \(k\)는 \(N\)의 \(p\)진법 자릿수 합과 같다.

$$ k = \left\lfloor \frac{N}{p} \right\rfloor + \left\lfloor \frac{N}{p^2} \right\rfloor + \cdots $$

답이 \(10^{1017}\)까지 커지는 경우가 있어서 Bigint나 python을 써야 한다.

 

 

BOJ 13875. Just In Time (Gold II)

 

Last update : 2019.12.16.

 

 

결국 함수 \(f : [n] \to [n]\)을 랜덤하게 고를 때, \(f^{(k)}(x) \neq x\)일 확률이 가장 높은 \(k \le n\)을 구하면 된다. \(k\)가 합성수면 무조건 손해고, \(k\)가 클수록 확률이 낮아진다. 따라서 답은 \(n\)이하의 가장 큰 소수.

 

결국 함수 \(f : [n] \to [n]\)을 랜덤하게 고를 때, \(f^{(k)}(x) \neq x\)일 확률이 가장 높은 \(k \le n\)을 구하면 된다. \(k\)가 합성수면 무조건 손해고, \(k\)가 클수록 확률이 낮아진다. 따라서 답은 \(n\)이하의 가장 큰 소수.

 

 

BOJ 16767. Convention II (Gold III)