5월 1주차 Weekly PS

• Google Codejam 2021, Round 1B
  • Broken Clock, Small-Middle
  • Subtransmutation, Full
• Problems
  • BOJ 20191 줄임말 (KOI 2020)
  • BOJ 3006 터보소트 (COCI 2007)

Apr 26 - May 09, 2021. 이번 주차는 4월 말 것들도 포함되어 있다. 이전 블로그에서 했었던 weekly PS를 다시 써보려고 한다. 알고리즘 공부도 요새 너무 못한거 같아서… 시험기간 2주씩을 제외하고, 5월에는 아마 1-4주차까지는 있을 예정이다.

Google Codejam 2021, Round 1B

1번 Broken clock의 small과 middle, 2번 subtransmutation의 small과 large를 풀고 1101등으로 1B를 통과했다. 올해는 Round 2에는 큰 의미를 두고 있지 않다 (요새 코딩 연습을 너무 못해서..)

놀라운 구현 뇌절이 있을 예정이었기 때문에 미연에 방지하고자 python으로 뛰었고, 그럼에도 불구하고 Broken clock 구현에 1시간 반 정도를 박고 9번을 제출했지만 large를 맞지 못했다는건 좀 충격적이다.

문제 풀이에 대해 간략히 얘기하자면…

Broken Clock, Small-Middle

Middle까지는 가능한 시간이 정수 초 만큼이라서 43,200가지밖에 없고, 이 모든 경우를 직접 확인해도 넉넉한 시간이다.

코드 : 링크

Subtransmutation, Full

왜 문제 순서가 이런지 잘 모르겠다. 넉넉히 $K$ 한개로 시작해서 만들 수 있는지를 매번 확인해도 시간이 넉넉하고, 이는 $K$부터 1번까지 거꾸로 오면서 Greedy하게 DP를 계산해주면 된다. 말이 조금 이상한데, 꼭 필요한 개수만큼 빼놓고 나머지는 전부 나중에 쓰일수도 있으니 작은걸로 분해해준다고 생각하면 간단하다. 말보다 코드가 훨씬 쉬운 문제.

코드 : 링크

Problems

BOJ 20191 줄임말 (KOI 2020)

난이도 : Gold 3 (BOJ)

문자열 S와 T가 주어질 때, T를 몇 번 concat해야 $T^n$ (concat) 이 $S$를 subseqeunce로 포함하는지 묻는 문제. S의 각 글자에 대해서, 이 글자가 T의 몇번째에 대응될 수 있는지 미리 모두 확인한다. Greedy하게, 내 이전 글자들보다 뒤에 있기만 하다면 대응할 수 있는 위치 중 최대한 앞에 대응해야 무조건 이득이 된다. 그러나 더이상 대응 가능한 위치가 없다면, 새로운 T를 하나 추가해서, 가능한 가장 앞에 대응해야 한다. 이를 이용하면 전처리 $O(S + T)$ 를 수행함으로써, $S$의 각 글자에 대해 $\log T$ 시간에 위치를 찾아줄 수 있으므로 $O(S \log T)$ 시간에 해결된다.

코드 : 링크

BOJ 3006 터보소트 (COCI 2007)

난이도 : Platinum 4 (BOJ)

세그먼트 트리에 각 element의 위치를 저장하고, segment tree를 이용하여 다이나믹하게 뭔가를 갱신하는 좋은 연습문제지만 기본적인 개념을 파악하고 나면 어렵지 않다. Segtree를 이용하면 구간 $(a, b)$ 의 1의 개수 (남아 있는 원소의 개수) 를 쉽게 셀 수 있다.

코드 : 링크