목록원주율외우기 (1)

Software Engineering Note

원주율 외우기

문제: PI / 동적계획법 원주율을 외운다는 스토리는 뒤로하고 문제의 핵심은 끊어읽는 모든 경우를 어떻게 처리해야할까? 이다. 어떻게 돌아가는지 좀 써보자. 앞에서부터 3을 끊고, 나머지 처리앞에서부터 4를 끊고, 나머지 처리앞에서부터 5를 끊고, 나머지 처리 뒷 부분, 나머지 처리들도 마찬가지로 반복된다. 그런데, 저걸 그때그때 모두 계산하면 너무 오래 걸리잖아? 어차피 중복이 있을 것같단 말이지.. 예를들어 8까지 읽었다고 치자. 그러면 처리:남은길이 = 8:N 이 될텐데, 이 조합으로 access할 경우가 있다는 거다. 그러니까 저런 경우는 한 번 계산한걸 저장해두고 써먹자.. 이렇게 해서 쥐어짠 코드는 다음과 같다. 대충 이런 그림.. int fn(string str) { int minCost =..
알고리즘/알고스팟 2015. 6. 28. 14:16
이전 Prev 1 Next 다음