dp가 어떻게 쓰이는지 직관적으로 와닿는 문제. ​ 1. 시간초과 코드 피자를 순서대로 위에서부터 들어갈 수 있을 때 까지 넣어보는 방식. *시간복잡도 O(피자수*오븐깊이) from collections import deque D,N=map(int,input().split()) oven=[9876543210]+list(map(int,input().split()))+[0] pizza=deque(list(map(int,input().split()))) #바닥임 bottom=D+1 i=100 for i in range(N): temp=pizza[i] for d in range(1,bottom+1): if oven[d]

1. i행 j열의 의미 dp[i][j]는, j번째로 들어온 숫자까지 더하거나 뺏을 때 i가 되는 경우의 수를 나타낸다. ​ 2. 점화식 dp[i][j](i는 0~20)는 dp[i][j-1]에서 j번째들어온 숫자만큼을 더하거나 뺀값을 추가해주는 형태로 진행된다. 말이 어려우므로 표로 설명한다. 숫자가 가능한 범위는 0~20이므로 표의 행은 21개, 열은 들어오는 숫자의 개수만큼 확보한다. 11 8 3 2 4 8 7 2 4 0 8 8 (1) 첫번째 input 8에 1을 넣는다 8 0 1 0 1 2 3 4 5 6 7 8 1 9 10 11 12 13 14 15 16 17 18 19 20 2) 두번째 input은 3이다. 첫번째 input에서 3을 더하고 빼주면 5와 11이 된다. 이 경우들을 더해준다. 8 3 ..

배낭문제와 유사한 dp문제. 배낭 ​ 앱 가치 == 메모리 무게 == 비용 1. 풀이 (1) dp[i][j] : i번째 앱까지 끌 수있고, j 비용까지 가능할 때, 최대 메모리 (2) 비용이 0인 앱도 있으므로 0열은 0으로 채우지 않도록 주의. (3) 최대 메모리를 찾는 문제이기 때문에 나올 수 있는 최대 비용까지 열을 확보해야한다. (4) 점화식 dp[i][j]는 두가지 값을 비교하여 큰값을 넣는다. 1) i-1번째 앱까지 끌 수 있는 상황. => dp[i-1][j] 2) i-1번째 앱까지 끌 수 있는 상황에서 i번째 비용만큼이 확보된 값에서 i번째 앱을 끄는상황. => dp[i-1][j-(i의 비용)]+(i의 메모리) 5. 특정메모리(M)이상의 값을 확보할 수 있을 때 최소 비용을 찾으므로 탐색하면..

1. 풀이 (1) 인접해있는 두 행렬부터 비교해가면서 점차 길이를 늘려간다. (2) dp[i][j] : i번째 행렬에서 j번째 행렬까지 곱했을 때 나올 수 있는 최소연산 (3) 점화식(3중포문) for l : i와 j의 차이. 1차이나는 것(인접한것) 부터 시작하여 늘려나간다 for i : 시작점 찾기 (j는 끝점) for k : i와 j 사이에 구분점 선택 (ex l이 4이고, 2~6을 탐색할 때 (2,3:6),(2:3,4:6),(2:4,5:6) 중 가장 작은것을 (2:6)으로 선택) ​ 2. 소스코드 #include #include #include #include using namespace std; // dp[i][j] : i에서 j행렬까지의 곱중 최소연산 int dp[501][501]; // li..

0. 문제 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다. 5원을 1개 사용해서 거슬러 준다. 거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세..

제한시간 내에 최대의 모금액으로 이동할 수 있는 방법? ​1. 풀이 (1) dp의 의미 행은 구간, 열은 시간이 되어서 dp[1][1]부터 시작. dp[i][j]의 의미는 i구간안에서 j시간까지 최대 모금액 (2) 점화식 dp[i][j]=max(dp[i-1][j- (i구간에서 도보이동 시간)]+ i 구간에서 도보이동으로 받는 기부금 , dp[i-1][j- (i구간에서 자전거 이동시간)] + i 구간에서 자전거이동으로 받는 기부금) (3) 유의사항 1. [j - (i구간에서 도보이동 시간)]이 음수가 나오면 안된다. 이러면 시작도 전에 출발한게 된다. 2. 2구간이 이상일때부터 dp[i-1][j- (i구간에서 이동시간)] ==0 이되면 안된다. 이는 아직 이전구간에서 이동을 완료하지 않은 상태이기 때문이다..

1. 상하 뒤집기 문제를문제에서는 왼쪽아래부터 오른쪽위 지점까지 이동하는것으로 되어 있으나, 어차피 경우의 수만 구하면되고, 대칭이므로 리스트의 형태에 맞게 왼쪽위(0,0)에서 오른쪽아래(R,C)로 가는것으로 생각한다. ​ 2. 가능한 경우를 삼차원에 저장 연속으로 꺾는것은 안된다. 이는 (이전)과 (이전전)의 이동에 따라 현재의 이동이 제한된다는 것을 말한다. 이를 고려해주기 위해 (i,j)위치에 이전 이동과 이전전 이동을 저장해야한다. 이를 위해 삼차원 배열을 활용한다. 다행히 이동은 최단거리로만 하기 때문에 오른쪽 or 아래로만 이동한다. 즉 가능한 경우의 수는 1) 아래 오른쪽 2) 오른쪽 오른쪽 3) 오른쪽 아래 4) 아래 아래 총 4가지로 볼 수 있다. 만약 상하좌우 모두 움직일 수 있다면 1..

배낭문제의 linear seacher는 다음과 같은 코드로 작성할 수 있다. def maxiValue(volume,index,value): global maxForPrune if index==N: if maxForPrune

1. 문제요약 (1) dfs,dp문제의 정석 (2) 사이클x (3) 가능한 경로의 개수(최단경로 아니다!) 2. 풀이 (1). 일단 가능한 경로를 모두 찾아야 하기 때문에 dfs로 모두 찾는다. (2). 초기값은 -1로 지정해준 후, 이때 한번 지나간 곳은 다시갈 필요가 없으므로 0으로 바꿔준다. (3). 이후 리턴을 받을때 +1씩 해준다 * 설명이 잘되어있는 블로그(단, 초기값이 0으로 되어있어서 시간초과가 난다) https://wootool.tistory.com/83 [백준][1520번][DP] 내리막길 내리막길 https://www.acmicpc.net/problem/1520 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

1. 풀이 (1) 각 성별을 정렬한다. 남자성격과 여자성격을 정렬했을 때 총 차이의 합이 최소가 되기위해선 항상 아래의 조건이 만족한다. (n번째남자와 매칭된 여자의 성격수치) j이면 j여자에게 잘맞는 여러명의 남자중 하나를 고른다 dp[i][j]=min(dp[i][j],d[i-1][j]) - ij: d[i][j]=min(d[i][j],d[i-1][j]) ..

1. 풀이 dp[i][j] : i에서 j문자열까지 만들 수 있는 길이 중 최대 dp[i][j]를 구하기 위해선 아래 두가지를 고려해주면 된다. ​ (1) (A[i]==a and A[j]==t) or (A[i]==g and A[j]==c) 인경우 dp[i+1][j-1]+2 => 양끝이 조건에 만족하면 KOI유전자 (2) dp[i][j]=max(dp[i][j-s]+dp[i+j+1-s][j] (k: 1~j-i)) => () + ()가 가능(각조합에서 최댓값 찾기) 2. 소스코드 A=input() size=len(A) dp=[[0 for j in range(size)] for i in range(size)] for j in range(1,size): for k in range(size-j): dp[k][j + ..