원주율 외우기

알고리즘 문제해결 전략1 239p에도 소개된 문제입니다.

(algospot 링크 https://algospot.com/judge/problem/read/PI)

문제를 풀고나니 중요한건 역시.

 문제를 완전히 이해하자

입니다.

처음에 3~5개씩 잘라 외운다는것을 간과 하고 한참을 고민했는데 

다시 보니 이해가 되었습니다.

제가 접근한 방법은 역시 동적계획법과 메모아이제이션을 이용하여 풀었습니다만,

풀고 순위를 보니 속도가 약 100ms로 40위권이더군요.

우선 코드 입니다.

앞으로 코딩할때 게시할 코딩 만큼은 변수명을 명확히 해야겠습니다.

main은 그냥 data얻는게 전부이며

중요한건 pi함수입니다. 

verify함수는 3~5개의 원주율의 부분 집합이 문제의 다섯가지 기준에 따라 몇점이 평가하는 함수 입니다. 

문제를 풀어나가는 핵심은 다음과 같습니다.

1. 이전에 어떤 숫자들이 있었는지는 알 필요 없습니다.

2. 어떤 자릿수 n부터 다시 외우기 시작할 때 

{ n , n+1, n+2 } 

{ n , n+1, n+2 , n+3 } 

{ n , n+1, n+2 , n+3 , n+4} 

를 각각 평가하고 이 중 제일 작은 점수를 더할 값으로 취합니다.

이때 각 부분집합에서 다시 pi함수를 호출하여 원주율 끝까지 탐색하게 만듭니다.

3. 이 문제에 적용 할 메모아이제이션기법은 어렵지 않습니다. 

2번처럼 어떤 자릿수 n부터 외워나가기 시작할 때 memo[n]이 -1이 아니라면 그 값을 리턴합니다.

memo를 적용할땐 n ~ m자릿수의 min을 결정할때 memo[n] = min을 적용하면 됩니다.

이를위해 pi함수 맨 마지막 ref에 적용하고 있습니다.

주의할점은 부분집합이 끝에 도달할때 1,2가 남아 있다면 여지까지 합산한 점수(외웠던 자릿수들)은 무효화 해야합니다.

이를 위해 기저사례에서 WRONG를 리턴하며 OK는 잘 도달 했을때 사례로 하였습니다.

책대로 하면 몇 ms가 나올지 모르겠지만 어쨋든 이 보다 더 좋은코드가 있을텐데 이는 또 나중에 게시물을 게재하겠습니다.