Euler (2) 썸네일형 리스트형 [Euler Project 091] 직각삼각형 갯수 구하기 (2) 주어진 레인지 안의 두 점을 잡아서 원점과 연결한 삼각형이 직각삼각형인 갯수를 구하는 문제임. 벡터의 내적과 외적의 성질을 이용해서 간단한 식으로 푼다. 내 컴퓨터에서 10초정도 걸린다. 아무래도 모든 가능한 점을 다 돌면서 검사를 하다보니.과거에 풀었던 것은 조건을 나눠서 복잡했었는데, 이 쪽이 코드는 더 간단하다. 비슷하게 풀었던 다른 문제도 있었던 듯. [Euler Project 078] 분할함수 (Partition Function) 76, 77번을 풀었던 방법으로 풀었는데, 끝까지 계산하지 못하고 오버플로우가 났다. 삼각형 형태로 메모리가 늘어나서 13000 까지 찍고 죽는 것이었다. 그래서 위키백과의 점화식을 이용하여 푸는 코드를 짜서 풀었다. 점화식은 2차원인 아닌 1차원으로 기억하고 있으면 되서 답을 내 줬다. 죽는 코드와 죽는 모습 #!/usr/bin/env python # euler 78 P = [] n = 0 P.append([]) P[n].append(0) # P[0][0] n = 1 P.append([]) P[n].append(0) # P[1][0] P[n].append(1) # P[1][1] n = 2 while 1: cnt = 0 P.append([]) for i in range(n+1): if i == 0: cn.. 이전 1 다음
