본문 바로가기

ProjectEuler

 (2)
[Euler Project 114] 몇 칸짜리 격자를 빨간색이나 검은 색으로 채운다. 이 조건만 있으면 단순히 2의 n승으로 답이 끝난다. 조건은 빨간색은 최소한 연속 3칸 이상 이어져 있어야 한다는 조건이 추가되어 문제가 복잡해진다. 제일 처음 칸 부터 한칸씩 빨간색을 칠할 지, 검은 색을 칠할지를 결정하는 함수를 구성했고, 이 함수를 재귀적으로 불렀다. 어차피 한 칸을 채운 다음에는 남은 몇 칸에 대해 고민하는 것은 똑같으니까. 이전에 빨간색이 아니었다면, 빨간색이 오면 3칸이 무조건 칠해진다. 경우의 수가 줄어든다. 그리고 마지막에 3칸 미만이 남아 있으면 무조건 검정색이 들어갈 수밖에 없다. 뭐 이런 조건들을 함수에서 분기해야 했다. 처음에는 완성된 격자를 다 프린트하는 함수를 만들어서 예시로 주어진 7칸 짜리를 해 봤고, 50을 ..
[Euler Project 164] 연속된 세 개의 자리수의 합이 9를 넘지 않는 20자리수 연속된 세 개의 자리수의 합이 9를 넘지 않는 20자리수의 갯수를 구하라. ( http://projecteuler.net/index.php?section=problems&id=164 ) def get_count(n1, n2, remain): #print " "*(20 - remain), n1, n2, remain if cache.has_key((n1, n2, remain)): return cache[(n1, n2, remain)] count = 0 sum = n1 + n2 if remain == 1: cache[(n1, n2, remain)] = 10 - sum return 10 - sum for n3 in range(10 - sum): count += get_count(n2, n3, remain - 1..

티스토리툴바