문제 파악
나열된 숫자들에 대해 일정한 규칙을 가지고 적절하게 구간을 나누는 문제이다. 구간을 나눠가면서, 난이도의 최소값을 구하는 문제기 때문에 부분 문제로 나뉘는 문제임은 어렵지 않게 파악되었다. 끊을 수 있는 구간 역시 3,4,5 세 구간 밖에 없었기 때문에 복잡하게 느껴지지 않아서 대략적인 설계는 간단히 마칠 수 있었다.
구간의 숫자들의 규칙에 따라 난이도가 결정되는데, 이 결정되는 방식을 C++ 자료 구조를 능숙히 다루지 못해 (string, integer간의 변환) 일일이 하드 코딩하느라 시간 소요가 많아졌다.
풀이와 내가 생각한 설계와 구조 자체는 거의 동일에 설계에는 큰 어려움을 느끼지 못했지만 구현 측면에 있어서 너무 많은 시간이 소요되었다.
문제 풀이
우선 두 함수가 필요한데 첫 번째는 부분 문제에 대한 재귀 함수이고 두 번째는 숫자 구간들에 대한 난이도 계산에 필요한 함수이다. 난이도 계산에 필요한 함수에 대해 나는 3,4,5칸 별로 나누어서 작성하느라 많은 시간이 소요 됐는데, 책의 풀이는 구간의 범위 자체를 인수로 받아서 substr과 string연산, mutex를 활용해서 간단히 해결했다.
숫자들의 마지막 근처에 도착했을 때 3 미만의 숫자가 남아 있는 경우는 올바른 구획이 아니므로 제외해야 하는데, 이 경우는 리턴 값을 매우 큰 값으로 해서 난이도 계산에서 자연스럽게 제외되게 했다. 재귀 함수 안의 for문이 남은 구간 밖으로 갈 경우 돌지 않기 때문에 자연스럽게 가장 큰 난이도로 설정된 수가 리턴된다.
느낀점
역시 다른 dp, 완전 탐색 문제들처럼 부분 문제 설정의 중요함을 느꼈고, 특히나 구현 과정에서 시간을 단축하기 위해서는 자료 구조와 그 자료 구조와 함께 자주 쓰이는 함수들에 익숙해 지는게 중요하다는 것을 느꼈다. string이나 int, vector 등 알고리즘 문제에서 늘 등장하는 자료 구조에 대해서는 그 컨테이너 클래스의 메서드들을 잘 익혀야겠다.
