1. 풀이 (1) dp도 모든 경우를 탐색하는 방법이다. (2) dp[case][a][b] : case번째에 왼쪽문이 a에 열려있고, 오른쪽문이 b에 열려있을때 까지의 최소이동 (3) case-1에서 case로 넘어갈 때, 맨하탄거리를 더해주어서 더 최솟값을 찾는다. ​ 2. 소스코드 N=int(input()) a,b=map(int,input().split()) a-=1 b-=1 size=int(input()) L=[0] for i in range(size): L.append(int(input())-1) maxNum=500 # dp[case][a][b] : case번째에 왼쪽문이 a에 열려있고, 오른쪽문이 b에 열려있을 때 최소이동 (a

1. 풀이 (N의 크기를 살펴보고 2차원이 가능하다면 2차원 dp를 떠올려보자..) ​ dp[i][j] : i자리수에서 j로 끝나는 계단 수의 개수 이때 i자리의 j로 끝나는 수는 i-1자리의 j-1로 끝나는수와 , j+1로 끝나는 수 끝에 j만 붙이면 되기때문에 두 경우의 수의 합으로 표현할 수 있다. (단 j가 0이면 1을, 9이면 8만을 붙일 수 있는것을 주의) ​ 따라서 아래와 같은 점화식을 만들 수 있다. dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1] ​ 2. 소스코드 N=int(input()) dp=[[0 for j in range(10)] for i in range(N+1)] for j in range(1,10): dp[1][j]=1 for i in range(2,N+1): ..

1. 풀이 dp[i][j] : i번째 동전까지 이용해서 j원을 만들때 가능 한 최소동전개수. i번째 동전까지 이용해서 j원을 만들때 가능 한 최소 동전개수는 i-1번째 동전까지 이용했을때 j를 만드는 경우와 (j-(i번째동전의 금액))최소동전수+1 한 경우 중 최소 값을 선택하면 된다. ​ 따라서 점화식은 아래와 같다 dp[i][j]=min(dp[i][j-i번째 동전의금액]+1,dp[i-1][j]) ​ 이때 dp를 2차원으로 만들었을 때 바로 위에 행과 비교를 하기 때문에 1차원 dp 리스트를 만들어도 상관이 없다. => 1차원 for문에서 i번째 반복을 마친 상태가 결국 2차원 dp의 i행 따라서 메모리를 최적화 시키기 위해 1차원으로 dp를 생성한다. ​ 2. 소스코드 n,k=map(int,input..

최소로 움직이는 횟수 = 전체명수 - 처음에 최대로 정렬되어있는 개수(LIS) LIS를 구성하는 요소를 제외하고는 모든 유치원생이 각자 한번씩은 반드시 움직여야 한다. N=int(input()) L=[] for i in range(N): L.append(int(input())) lis=[1 for i in range(N)] for i in range(1,N): for j in range(0,i): if L[j]

1. 풀이 (1) dp[i][j] : A의 i번째, B의 j번째 문자열까지의 최장 공통 문자열의 수 (2) A[i]와 B[j]가 같다면? 왼쪽위(그전까지의 최장공통문자수)에서+1 (3) 다르다면? 위,왼쪽숫자중 최대수 ​ 2. 소스코드 A="0"+input() B="0"+input() sizeA=len(A) sizeB=len(B) dp=[[0 for i in range(sizeB)] for j in range(sizeA)] for i in range(1,sizeA): for j in range(1,sizeB): if A[i]==B[j]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) print(dp[sizeA-1][sizeB-1])

1. 풀이 3번연속은 안된다. 따라서 경우의 수를 다음과 같이 나눈다 ​ (1) i번째를 마시고 i-1번째를 마시는경우 -> (i번째) + (i-1번째) + (i-3번째까지 최대) (2) i번째를 마시고, i-1번째를 마시지 않는 경우 -> (i번째) + (i-2번째까지 최대) (3) i번쨰를 마시지 않는경우 -> (i-1번째까지 최대) ​ 2. 소스코드 N=int(input()) dp=[0 for i in range(N+3)] preNum=0 for i in range(3,N+3): nowNum=int(input()) # i번째와 i-1번째를 마시는 경우 a=preNum+nowNum+dp[i-3] # i번째를 마시고, i-1번째를 마시지 않는 경우 b=nowNum+dp[i-2] # i번째를 마시지 않는..

https://blog.naver.com/ngoodsamari/221776557221 행렬곱셉순서와 비슷한 문제. 1. 풀이 (1) 단 두개가 남았을 때 부터 생각해서 N개의 카드가 있을 때 까지 확장한 후 최적의 선택을 찾는다. (2) dp[i][j] : i~j를 뽑았을 때 근우가 얻을 수 있는 최대 점수 (3) 근우가 항상 먼저 뽑기 때문에 현재까지 뽑은 카드의 개수(N-(j-i+1))가 짝수이면 근우차례이고, 홀수이면 명우차례이다. (4) 명우도 항상 최적의 선택을 하기 때문에, 명우차례일때는 근우입장에서 최소의값을 선택해야 한다. ​ 2. 소스코드 #include #include #include using namespace std; int L[1000]; // dp[i][j] : i~j를 뽑았을때..

1. 풀이 더보기 시작점, 열쇠가 있는 모든 지점에서 로봇이 복제되고, 모든 열쇠를 얻어야 하며, 이때 모든 로봇의 이동거리를 구한다. 위의 문제가 MST문제임을 알면 구현은 매우쉽게 일반적인 MST를 푸는것과 같이 하면 된다. 하지만 위의 문제 MST문제인지를 알기가 어렵다. 따라서 조건을 어느정도 외워두고 비슷한 상황에서 MST를 떠올릴 줄 아는것이 중요해 보인다! 2. 소스코드 from collections import deque import sys dR=[0,0,-1,1] dC=[1,-1,0,0] N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) def dist(sR,sC,fR,fC): q=deque([[sR,..

1. 풀이 (1) N번째의 상태를 확인하기 위해 N-1번수행한 후의 맵을 구현한다. (2) d[i][j] : 현재 맵의 상태. 0이면 아래, 1이면 오른쪽 (3) d[i][j]에 N번 존재하면, d[i+1][j], d[i][j+1]에 N/2번 존재한다. 이때 d[i][j]가 아래이면 d[i+1][j]가 추가로1이 더해지고, 오른쪽이면 d[i][j+1]가 추가로1 더해진다. (4) 최종맵은 홀수이면 오른쪽(1)이고, 짝수이면 아래(0)이므로 2로 모듈러연산을 해준다. (5) 최종답을 구하기 위해 N번째 산책을 시작한다. ​ 2. 소스코드 #include #include #include using namespace std; int d[1002][1002]; int map[1002][1002]; int mai..

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). O(NM)이고 제한시간 5초(C++기준) 이므로 살짝 애매한데 최적화가 잘 안된것 같다. stack으로 풀었고 pypy로 제출하여 정답. (소스코드2) ​ 2.소스코드 (1) 소스코드1 (시간초과) import sys from collections import deque N,M=map(int,input().split()) graph={} for i in range(1,N+1): graph[i]=[] for i in range(M): A,B=map(int,sys.stdin.readline().rstrip().split()) graph[B].append(A) hackCom=0 ans=[] for start in range(1,N+1): visite..