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..

1. 풀이 일반적인 mst문제이고, N개의 노드를 모두 연결하는 edge를 만들어서(nC2개) 크루스칼을 적용하면 정답은 맞지만 시간초과가 발생한다. (소스코드1)​ 시간초과를 줄일 수 있는 방법은 아래의 조건을 이용해서 사용하는 edge의 개수를 줄이는것. (소스코드2) 더보기 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 그리고 위조건을 이용하는 방법은 아래와 같다. (1) 1차원 좌표에서 N개의 점이 있고, 이때 N개의 점으로 mst를 만드는 방법은 왼쪽부터 i번째 점을 i+1번째 점과 연결해나가는 방법이다. (n-1개) (2) 3차원에서도 똑..

1.풀이 (1) 주어진 선후관계만으로 q와 graph를 구성한다 (2) q에 있는 요소 중 가장 작은(가장 쉬운)것을 pop하면서 진행한다 => heap을 쓴다. ​ * 두가지풀이 - 소스코드1(시간초과) : toNode와 fromNode를 사용. fromNode를 하나씩 삭제하고 fromNode가 비어있을때 pq에 넣음 - 소스코드2 (통과) : toNode와 들어오는 노드의 개수(cntParent)를 사용. cntParent 0이 될때 pq에 넣음 ​ 2. 소스코드 (1) 소스코드1 (python3 시간초과) import heapq N,M=map(int,input().split()) fromNode={} toNode={} for i in range(1,N+1): fromNode[i]=[] toNode..

1. 풀이 (1) 늦게 끝낼 수 있는 일부터 탐색하여 최대한 늦게 시작한다. (2) (1)에서 탐색한 일이 이전의 일의 데드라인에 영향을 주면, 이전의 일을 영향받는만큼 늦게 시작한다. 2. 소스코드 N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) def returnSecond(L): return L[1] L.sort(key=returnSecond) preStart=L[N-1][1]-L[N-1][0] for i in range(N-2,-1,-1): if preStart

1. 풀이 모든 문제는 푸는데 1시간이 걸리기 때문에, 컵라면을 가장 많이주는걸 그리디하게 고르면 된다. 이때 문제마다 데드라인이 다르기 때문에 시간을 뒤에서부터 1시간 단위로 탐색하면서 먼저 끝나는 일 중에 컵라면을 많이 주는 것부터 차례대로 수행하면 된다. 2. 소스코드 from collections import deque import heapq N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) # t시간까지 해야되는거 pq에추가 def addPQ(t): while(L): dead,cup=L.pop() if dead==t: heapq.heappush(cupPQ,-1*cup) else: L.append([dea..