동적프로그래밍

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 코드 My answer # 메모리 49440 KB / 시간 1516 ms import sys input=sys.stdin.readline t_c=int(input()) for k in range(t_c): n=int(input()) sticker=list(list(map(int,input().split())) for _ in range(2)) dp = [[0]*(n+1) for _ in range(2)] dp[0][1],dp[1][1]=stick..

문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 코드 My answer import sys input=sys.stdin.readline n=int(input()) num=list(map(int,input().split())) dp=[0]*n for i in range(n): if(num[i]>=0):dp[i]=max(0,dp[i-1])+num[i] else: if(dp[i-1]+num[i]>=0): dp[i]=dp[i-1]+num[i] else: dp[i]=num[i] print(max(dp)) Another an..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 My answer import sys input = sys.stdin.readline n=int(input()) dp=[0]*n dp[0]=1 array=list(map(int,input().split())) for i in range(1,n): tmp=[dp[j] for j in range(i) if(array[j]

문제 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 코드 My answer import sys input = sys.stdin.readline n=int(input()) dp=[0]*(n+1) array=[] for i in range(int(n**0.5)+1): dp[i*i]=1 for i in range(1,n+1): for j in range(1,int(i**0.5)+1): if(dp[i]==0):dp[i]=dp[j*j]+dp[i-j*j] else: dp[i]=min(..

📖문제 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 입력 조건 첫째 줄에 N, M이 주어진다. (1 d[2]=1 5. d[3] -> d[0],d[1]이 존재하나, 둘다 -1 그리고 현재 d[3]=1---------------> d[3]=1 6. d[4] -> d[1],d[2]가 존재하고, d[2] != -1이며 현재 d[4]=-1 이므로, d[4]=d[2]+1(2를 만드는 방법에 화폐2 추가) --..