Dp

백준 2579번 바로가기 나의 풀이 s = [] for _ in range(n:=int(input())): s.append(int(input())) points = [0]*n if n < 3: print(sum(s)) else: points[0] = s[0] points[1] = s[0] + s[1] points[2] = max(s[1]+s[2],s[0]+s[2]) for i in range(3,n): points[i] = max(points[i-2], points[i-3]+s[i-1]) + s[i] print(points[-1]) CODE REVIEW 중학교 창의력 수학 경시대회 단골소재 계단 오르기. 한 계단 또는 두 계단이라는 표현은 질릴도록 봤다. case별로 쪼개서 점화식을 설정하고 풀어내면 된다. 전 단계를 밟는 경우와/밟지 않는 경우로 나누면 모든 경우를 커버할 수 있다. max(points[i-2], points[i-3]+s[i-1]) 부분이 조금 까다롭긴 했는데 그외에는 무난한 문제였다.

백준 17175번 바로가기 나의 풀이 x,y=1,1 for i in range((n:=int(input()))-1): x,y=y,(x+y+1)%1000000007 print(1 if n<2 else y) CODE REVIEW 피보나치 수열 함수가 호출되는 횟수를 구하는 문제였다. fibo(n)을 호출하면 fibo(n-1), fibo(n-2)가 호출되므로, 총 횟수는 1(자기자신) + fibo(n-1) + fibo(n-2)로 구할 수 있다. f[n]=1+f[n-1]+f[n-2]로 구현해도 되지만, x,y=y,(x+y+1)로 구현하면 메모리를 아낄 수 있다.

백준 6571번 바로가기 나의 풀이 import sys f = [1,2]+[0]*1002 for i in range(2,1004): f[i] = f[i-1] + f[i-2] for i in sys.stdin: a,b=map(int,i.split()) if a==0 and b==0: break count = 0 for i in f: if a<=i and i<=b: count += 1 print(count) CODE REVIEW 주어진 범위에 해당하는 피보나치 수의 개수를 구하는 문제였다. 시간을 줄이기 위해서 미리 1004개에 해당하는 피보나치 수열을 구하고 범위에 속하는지 판단하는 방식으로 코드를 구현했다.

백준 9711번 바로가기 나의 풀이 f = [0,1,1]+[0]*10002 for i in range(2,10004): f[i] = f[i-1] + f[i-2] for i in range(int(input())): p,q=map(int,input().split()) print(f"Case #{i+1}: {f[p]%q}") CODE REVIEW 실버3 맞나 싶은 문제. 단순히 범위에 맞게 피보나치 수열을 구해주고 출력 형식에 맞추어 print해주면 끝이다.

백준 1003번 바로가기 백준 피보나치 함수 문제를 뿌셔보자 프로젝트!! 나의 풀이 def fibo(n): a,b=1,0 for i in range(n): a,b=b,a+b return [a,b] for i in range(int(input())): print(*fibo(int(input()))) CODE REVIEW 규칙성을 찾아보니 fibonacci(0)과 fibonacci(1)이 출력되는 횟수가 각각 피보나치 수열을 이루었다. 이제는 조금 신박한 피보나치 수열 문제를 풀어보고 싶다…