DP

2096 백준 파이썬

dp지만 4MB 메모리 제한이 있다. dp 배열을 선언하려면, 아니 애초에 입력한 값을 배열에 등록하려면 n의 제한이 100,000까지이므로 4*3*100,000byte가 필요하다. 이건 12MB이므로 진작에 메모리 초과가 일어난다. 3개짜리 배열을 선언해서 해결했다. import sys input = sys.stdin.readline n = int(input()) maxdp=[0,0,0] mindp=[0,0,0] tmp1=[0,0,0] tmp2=[0,0,0] for _ in range(n): a,b,c=map(int,input().split()) for x in range(3): if x==0: tmp1[0]= a+ max(maxdp[x],maxdp[x+1]) tmp2[0]= a+ min(mindp[x..

9084 백준 파이썬

동전으로 돈만들기. 1,2로 7을 만드는 경우를 살펴보면, 1+6을 만드는 경우의 수 2+5를 만드는 경우의 수가 있다. 그런데 이걸 1과 2를 동시에 진행시키면 중복되는 경우가 세지게 된다. 그래서 결론적으로는 피보나치수열처럼 된다. 아래는 잘못 작성한 코드이다. t = int(input()) for i in range(t): n = int(input()) l = list(map(int, input().split())) m = int(input()) dp = [0 for i in range(m + 1)] dp[0] = 1 for x in range(1, m + 1): for t in l: if x - t >= 0: dp[x] += dp[x - t] print(dp) 이것을 1과 2의 경우를 분리해서 진..

21600 백준 파이썬

말만 번지르르하지 별거 없다. 파란 영역 중에 제일 큰 계단을 찾으라는 문제. 아직 스위핑을 안배워서 기본 점수만 받아 보았다. 경우에 따라 잘 나눠서 코딩해주면 된다. 1. 이전값 보다 큰 경우 이전 dp값 +1 2. 이전값과 같은 경우 이전 dp + 0 3. 이전값보다 작을 경우 이전 dp값이 현재 높이보다 작은 경우 : 이전 dp+1 이전 dp값이 현재 높이와 같은 경우 : 이전 dp +0 이전 dp값이 현재 높이보다 클 경우 : 현재 높이값 n=int(input()) h=[0] h.extend(map(int,input().split())) dp=[0 for _ in range(n+1)] dp[1]=h[1] for x in range(1,n+1): if h[x]>h[x-1]: dp[x]=dp[x-1..

21317 백준 파이썬

작은 점프, 큰 점프 그리고 단 한번의 매우 큰 점프를 통해 마지막 돌로 가는 최소 에너지를 구하는 문제. 우선 단 한번의 매우 큰 점프를 제외하고 생각했다. 단 한번은 예외처리를 해주면 되니까 라는 생각에서 그랬다. n까지 가는데 드는 최소 에너지 dp(n)은 dp(n-1)+작은점프, dp(n-2)+큰점프 중 큰 값이다. 코드로 구현하면 n=int(input()) d=[[0,0]] for _ in range(n-1): d.append(list(map(int,input().split()))) dp=[0 for x in range(n+1)] if n==1: print(0) exit() elif n==2: print(d[1][0]) exit() dp[2]=d[1][0] dp[3]=min(d[1][0]+d[2..

2073 백준 파이썬

개인적으로 굉장히 어려웠던 문제... 첫째로, 최대 수도관 용량으로 dp를 할지, 길이로 dp로 할지 정한다고 해맸다. 두번째로, 입력받아서 배열에서 꺼내쓰려다가 시간초과로 쳐맞았다. 세번째로, 중복사용때문에 고생했다. 아무튼 코드는 아래와 같다. 초기화 방법은 입력값이 1이라고 하면 dp[1]이 들어가는 모든 값의 합을 바꾼다. x가 7이라고 한다면, dp[7]=min(1,dp[7-1])이다. 그리고 만약 dp[7]이 입력이 들어오면 변경 해주는 방식이다. d, p = map(int, input().split()) dp = [0 for _ in range(d+ 1)] for _ in range(p): l, c = map(int, input().split()) for x in reversed(range(..

2225 백준 파이썬

0부터 n까지의 정수 k개를 더해서 n이 되는 경우의 수를 구하는 프로그램 뭔가 고등학교 시절의 자연수 분할이 떠오른다. 차이점은 0도 포함한다는 점 예를들어 0부터 9까지 2개로 나타내면 0+0 1+0, 0+1 2+0, 1+1, 0+2 3+0, 1+2, 2+1, 0+3 4+0, 1+3, 2+2, 3+1, 4+0 5+0, 1+4, 2+3, 3+2, 4+1, 5+0 ... 와 같이 (n,2)=n+1임을 알 수있다. 그리고 잘 보면, 1+ n-1, 2+n-2꼴로 나타 낼 수 있는데, 이를 잘 보면 (n,k)=(n-1,k-1)+(n-1,k-2)...(n-1,0)으로 나타낼 수 있음을 알 수 있다. 가로는 숫자, 세로는 k개로 나타 낸 것이다 0 1 2 3 4 1 1 1 1 1 1 2 1 2 3 4 5 3 1 ..

10571 백준 파이썬

요약하면, 무게가 커지고, 선명도 값이 감소하는 최장수열을 구하라는 것 여타 다른 dp문제와 동일하되, 두가지 값을 동시에 비교한다. 반복문을 통해 0부터 n까지 기준값을 높히고, 0부터 x까지 비교값을 바꿔가며 무게와 서명도를 비교하고, 그에따라 compare 배열에 값을 바꿔준다. 출력은 compare의 최대값을 출력해주면 된다. t=int(input()) for _ in range(t): n=int(input()) compare=[1 for x in range(n)] w=[] c=[] for _ in range(n): a,b=map(float, input().split()) w.append(a) c.append(b) for x in range(n): for y in range(x): if w[x]>..

1660 백준 파이썬

캡틴 이다솜 문제를 고민하기에 앞서 사면체에 들어가는 대포알의 갯수를 고민해 보자. 1개, 4개, 10개, 20개... 다음은? 우선 밑면을 생각해 봤을때, 밑면에 추가되는 삼각형이 점점 커짐을 알 수 있다. n이 300,000이라고 해서 300,000까지 다 구해놓기에는 우리에게 주어진 자원은 한정적이므로, 다른 방식으로 구해보자. 결국 우리는 n보다 같거나 많은 양의 대포가 쌓여있는 사면체가 처음 등장하기까지 구해야 한다. 그러므로, 이렇게 세울 수 있다. n=int(input()) tri=[1,3] d=[1,4] idx=1 while n>d[-1]: idx+=1 tri.append(tri[idx-1]+(tri[idx-1]-tri[idx-2])+1) d.append(d[idx-1]+tri[idx]) ..