PI

■ 문제

원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽어, 최소 난이도를 계산하는 문제이다.

각 조각들의 난이도는 다음과 같이 정해진다.

1. 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1

2. 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2

3. 두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4

4. 숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5

5. 그 외의 경우 난이도: 10

■ 풀이

풀이 핵심은 아래 2가지 조건을 구현하는 것이다.

1. 주어진 수열을 쪼개는 모든 방법을 하나씩 만들어 보고

2. 그중 난이도의 합이 가장 작은 조합을 찾아낸다.

1. 주어진 수열을 쪼개는 모든 방법을 하나씩 만들기

- 길이 3인 조각 난이도 + 3글짜 빼고 나머지 수열에 대한 최적해
- 길이 4인 조각 난이도 + 4글짜 빼고 나머지 수열에 대한 최적해
- 길이 5인 조각 난이도 + 5글짜 빼고 나머지 수열에 대한 최적해

2. 그중 난이도의 합이 가장 작은 조합을 찾기

난이도 합이 가장 낮은 조합을 찾는건 위 식을 점화식으로 표현하면 된다.
부분 수열의 위치를 start하고 할 때, 최소 난이도를 반환하는 함수 pi를 점화식으로 나타대면 다음과 같다.

pi(start) = min( classify(start, offset)  +  pi(start+offset) )
    - offset은 부분 수열 위치 start를 포함하는 조각 길이(3~5)를 말하며, 
    - classify는 해당 조각의 난이도를 반환하는 함수이다.

한 번 방문했던 위치는 재방문시 항상 동일한 최소 값을 반환하므로, 메모이제이션 적용이 가능하다.
위 점화식의 일부 상황을 그림으로 표현하면 아래와 같다.

실제 코드로 구현하는데 경계값 포함 여부를 결정하는게 항상 헷갈린다. 점화식을 시각화하여 경계값 포함 여부를 명확히 하고자 한다.

① PI 함수 내 재귀 조건

start + offset > A.length() 이면 for문 break;
 = start + offset <= A.length() 이면 실행

② PI함수 기저 조건 중 start == A.length()와 같다면 0을 반환해야 한다.
    classify가 배열 A 끝에(A.length() -1) 딱 도달하게 되면, PI(A.length)를 호출하기 때문이다.

③ 정수형 오버플로로 인한 MAX 값 오류(아주 큰 음수로 저장되는 오류)
    start = 3, offset = 4인 경우, pi(7)이 호출되어 INF값을 반환한다. 이 때, pi(7)이 반환한 INF값과 classify(3,4)가 반환한 값을 더하면 정수형 오버플로가 발생하여 메모이제이션에 오류가 생긴다.
    따라서, pi(start)가 INF 값을 반환할 때 아닐 때를 나누어 처리를 해줘야 한다.

이 알고리즘은 최대 n개의 부문 문제가 있고, 부문 문제를 해결하는 데 최대 세 개의 부문 문제를 포함한다. 따라서, 시간복잡도는 O(n)이다.