문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 import sys sys.setrecursionlimit(10**8) memo = {} memo[0] = 0 memo[1] = 1 memo[2] = 1 def dp(i): if i not in memo: if i%2==0: memo[i] = (dp(i//2) * (dp(i//2) + 2*dp(i//2-1)))%1_000_000_007 else: memo[i] = (dp(i//2)**2 + dp(i//2+1)**2)%1_000_000_007 return memo[..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 n = int(input()) numbers = list(map(int,input().split())) memo = [0]*n for i in range(n): target = [0] for j in range(i): if numbers[j] < numbers[i]: target.append(memo[j]) ..

문제 https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 n,k = map(int,input().split()) save = {} save[1] = ["1"] save[2] = ["1+1","2"] save[3] = ["1+2","1+1+1","2+1","3"] for i in range(4,12): save[i] = [] for j in save[i-1]: save[i].append(j+"+1") for j in save[i-2]: save[i].append(j+"+2") ..

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 a = [int(input()) for i in range(int(input()))] target = max(a) save = [1] * (target + 1) save[1] = 1 save[2] = 2 save[3] = 4 for i in range(4,target+1): save[i] = (save[i-1] + save[i-2] + save[i-3])%1000000009 for i in a: print(save[i]%100000000..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 n = int(input()) memo = {} memo[1] = 1 memo[2] = 1 memo[3] = 1 memo[4] = 2 memo[5] = 2 def a(i): if i not in memo: memo[i] = a(i-1) + a(i-5) return memo[i] for i in range(n): print(a(int(input()))) 단순한 DP 문제이다. N이 1~5일때는..