sm 기술 블로그

T = int(input()) result = [] arr = [0] * 1001 for _ in range(T): N = int(input()) arr[1], arr[2], arr[3] = 1, 1, 1 for i in range(4,N+1): arr[i] = arr[i-2] + arr[i-3] result.append(arr[N]) print("\n".join(map(str,result))) 문제요약 작은삼각형이 나선형으로 커지는데 입력값에 따른 삼각형의 개수를 구하시오. 설명 매우 쉬운문제이다. P(N)에 따른 개수는 다음과 같으며, 3까지는 1로 그 이후에는 P(N) - 2 + P(N) - 3 의 피보나치형태를 띄운다. 따라서 arr[i] = arr[i-2] + arr[i-3] 이 로직을 통해 쉽..

문제요약 입력된 값을 자릿수로 하여 이진수에서 00 이 붙어 있거나 아예 없는 모든 경우의 수에 15746을 나눈 나머지를 구하라. 설명 먼저 이 문제를 이해하고 규칙을 찾는건 크게 어렵지 않다. 다음과 같이 피보나치수열을 이루고 있음을 알고 있다. 피보나치 하면 먼저 재귀함수가 떠 오를 것이다. 동적프로그래밍 파트에다가 숫자가 매우 크므로 동적을 적용해 보았다. N = int(input()) memo = [0]*500 def Tile(N): if N == 1 or N == 2: memo[N] = N return memo[N] memo[N] = Tile(N-1)+Tile(N-2) return memo[N] print(Tile(N)%15746) 결과는 실패였다. 다음과 같이 메모리 초과 혹은 런타임 에러가..

TOP - DOWN 방식 result = "" memo = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)] def w(a,b,c): if a 20: return w(20,20,20) if memo[a][b][c] > 0 : return memo[a][b][c] if a < b < c : memo[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) return memo[a][b][c] memo[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) return memo[a][b][c] while True: a,..

본 코드는 pypy3로 제출해야합니다. n = int(input()) cntFib = 0 cntFib2 = 0 memo = [0 for i in range(100)] def fib(n): global cntFib if n == 1 or n == 2: cntFib += 1 return 1 else: return fib(n-1)+fib(n-2) def fibonacci(n): global cntFib2 if memo[n] > 0: cntFib2 += 1 return memo[n] if n