본문 바로가기

알고리즘 문제풀이

Kickstart 2018 Round H

올해의 마지막 Kickstart인 Round H에 참가했다. 세 문제 중A와 B는 무난하게 해결했지만, C는 계속 해매다가 어찌어찌 small밖에 해결하지 못했고, large는 시간 (8분) 초과로 기회가 날아갔다. 아무튼 제대로 해결한 두 문제의 풀이를 적어 보았다. (코드가 궁금하다면 Github 참고)

A. Big Buttons

하나의 금지된 접두어가 주어졌을 때, 그 뒤로 어떤 문자열이 오더라도 금지될 것이다. 즉, 길이 $L$인 금지된 접두어가 주어진다면, $2^{N-L}$개의 문자열들이 금지된다. 그렇다면 금지된 접두어들이 여러 개 있다면 어떻게 해야 할까? 접두어 사이의 포함 관계를 고려해야 한다. 예를 들어, BRRBR로 금지되는 문자열들은 (BRRBRB..., BRRBRR...) 모두 BRR로 인해 금지되는 문자열에 포함된다. 그러므로, 중복을 피하기 위해 주어진 다른 접두어로 시작하는 접두어는 고려하지 않아야 한다. 서로 포함되지 않는 접두어라면 어떻까? 금지되는 문자열들이 중복되지 않음을 쉽게 알 수 있다. 그러므로,

1. 다른 접두어로 시작하는 접두어들을 제외하고

2. 각 접두어로 인해 금지되는 문자열들의 개수($2^{N-L}$)를 모두 더하여

금지되는 문자열들의 개수를 구할 수 있다. 문제에서는 허용되는 문자열의 개수를 출력하라 하였으므로, $2^N$에서 금지된 문자열들의 개수를 뺀 값이 정답이다.


B. Mural

개인적으로 B는 알고리즘을 떠올리는 것 보다도 영어 독해가 어려운 문제였다. 언제나 양 끝의 벽만이 무너지고, 벽은 연속해서 칠해야 하므로, 최종적으로는 연속된 $\lceil \frac{N}{2} \rceil$개의 벽을 칠하게 된다. 이렇게 연속해서 칠했을 때 얻는 점수의 최댓값은 연속 합을 이용해서 쉽게 구할 수 있다. 잠시 고민해보아야 할 것은 앞에서 제시한 최댓값을 얻도록 벽을 칠하는 것이 벽이 무너지는 순서와 무관하게 가능한지다.

색칠된 벽들을 칠해야 최대 점수를 얻는다고 할 때, 파란색으로 표시한 벽을 (두 개가 파란색으로 표시된 경우는 무엇을 골라도 상관이 없다는 의미다) 처음으로 칠한 뒤, 양쪽 끝 벽 중 무너지는 방향으로 (예를 들어, 오른쪽 끝 벽이 무너지면 지금까지 칠한 벽들의 오른쪽을 칠한다) 칠해나가면 원하는 벽들이 무너지기 전에 칠할 수 있게 된다. 사실 문제에서 벽을 칠하는 방법을 제시하라 하지는 않았으므로 중요하지는 않지만, '이론상' 최댓값이 실제로/언제나 가능한지는 꼼꼼히 짚고 넘어갈 필요가 있다.