RUN@KAIST 7/9 방학 연습 풀이

1. 숫자카드

간단한 동적 계획법이다. 문자열을 길이 1 / 길이 2의 문자열로 분해하는 경우의 수를 세는 것인데, dp[i] = 앞 i자리 문자를 모두 분해하는 경우의 수라고 하면, dp[i-1]과 dp[i-2]에 대한 점화식이 나오고, 이를 통해 해결할 수 있다.

2. 놀이공원

배열을 통해서 각 1분 단위의 시간에 휴식이 가능한지를 관리한다. 놀이기구 하나에 대해서, (시작 시간 - 10분) ~ (종료 시간 + 10분) 동안은 휴식이 불가능하다. 고로 각 놀이기구 마다 이 구간에 체크해 두면, 해당 단위 시간에 휴식이 가능한 지 알 수 있다. 이 정보를 안다면, 

이 정보를 안다면, 가장 긴 휴식 가능 구간을 구하는 문제는, 0과 1로 이루어진 배열에서, 가장 긴 0으로 이루어진 연속 구간을 구하는 문제가 된다. 배열을 시작점에서 끝까지 계속 돌면서, 0이면 현재 구간의 길이를 늘려주고, 1이면 구간의 길이를 0으로 초기화하는 식으로 하면, 해당 위치를 끝점으로 가지는 구간의 최대 길이를 계속 관리할 수 있다. 그 중 최댓값을 구해주면 된다.

3. 신성 문자

사실 비뚤어져 있다는 게 정확히 무슨 뜻인지 이해하기 힘들긴 하지만... 아무튼 상식적인 선에서 각각의 문양을 비교하는 방법은, 각 문양의 안에 들어 있는 "흰 구멍" 의 갯수를 세는 것이다. 우연하게도 각각의 문양이 가지는 흰 구멍의 개수가 0 1 2 3 4 5개로 서로 다르기 때문이다. flood fill로 이를 구현하면 해결할 수 있다.

4. 이진 검색 트리

왜 냈지... 이진 검색 트리의 inorder traversal은 주어진 배열을 오름차순하면 쉽게 구할 수 있다. 고로 6/29 방학 연습의 2번 문제와 똑같이 풀 수 있다. 사실 정렬을 굳이 안 해도 되지만 뭐..