길이가 N인 문자열 S를 3개의 문자열로 나눈 후, 주어진 조건에 따라 점수를 계산하는 문제입니다. 점수는 문자열의 모든 부분 문자열의 순서에 따라서 결정 됩니다.
나눌 수 있는 모든 경우의 수 중에서 최대 점수를 얻을 수 있는 문자열을 찾는 문제입니다. 더불어 문자열의 길이의 최대 100 ****정도로 짧기 때문에 가능한 모든 부분 문자열을 확인하는 완전 탐색으로 문제를 해결할 수 있습니다.
문제 해결을 위해서 필요한 단계는 다음과 같습니다.
조합은 순서를 고려하지 않고, 집합에서 일부 원소를 선택하는 방법입니다. 예를 들어, [1, 2, 3]에서 2개를 고른다면, [[1, 2], [1, 3], [2, 3]]와 같이 나타낼 수 있습니다. 뽑는 순서를 고려하는 경우는 순열이라고 합니다. 조합과 순열은 완전 탐색 문제에서 모든 경우의 수를 찾는 방법이기 때문에, 구현 방법을 알고 있으면 도움이 됩니다.
보통의 조합은 재귀 함수로 구하지만, 이 문제는 크기가 작기 때문에 반복문으로 해결할 수 있습니다.