1. 풀이 (1) i+j+k=x를 i+j=x-k로 바꿔서 생각한다. (i번째수 + j번째수 = x번째수 - k번째수) (2) x가 가능한지 확인: k가 0번째부터 x-1번째까지 한번돌면서 (x번째-k번째)가 가능(방문되었는지)한지 확인 (3) x까지 추가되서 만들수 있는 숫자 최신화 : j가 0번째부터 x번째까지 돌면서 새로운숫자 (x번째+j번째)를 방문 * Ai의 범위는 -100000~100000이므로 x-k의 범위는 -200000~200000. 따라서 이를 리스트 인덱스로 만들어주려면 0~400000아 되므로 isPossible 리스트는 400001로 초기화 (4) (2),(3)의 과정을 N번반복. O(N^2) ​ 2. 소스코드 N=int(input()) L=list(map(int,input().sp..

파스칼의 삼각형으로 조합을 구할 수 있다. 위의 삼각형 형태를 행렬로 바꾸면 하삼각행렬로 만들 수 있다. (i,j)위치의 값이 정확히 iCj가 되는 예쁜 형태가 된다. (j==0일때만 1을 넣어주면된다.) ​ ex)[boj]11051_이항계수2 #include #include using namespace std; long long pascal[1000][1000]; int main() { int N, K; int max = 10007; cin >> N >> K; for (int n = 0; n

1. 풀이 (1) 약 한알을 다먹었을때 w, 반개만 먹었을때 H이므로 나올수있는 경우는 약이 2개일때 WWHH를 적절히 조합한 경우. (2) 이때 고려해야할 점은 약이 반개가 남으려면 그 전에 한개를 쪼갠적이 있어야한다. 즉 앞에서부터 순서대로 진행할 때 H의 개수가 W의 개수보다 많으면 안된다. (HW(X),WHH(X),WHWHH(X)) (3) 따라서 아래와 같은 점화식을 만들 수 있다. DP[i][j] : 알약반개 i번, 알약한개를 j번 먹었을때 경우의 수 그리고 이는 알약반개를 i-1번먹고, 알약한개를 j번먹은상태 (dp[i-1][j]) 에서 알약 반개를 먹는경우 + 알약한개를 i번먹고, 알약반개를 j-1번먹은상태(dp[i][j-1])​ 에서 알약 한개를 먹는경우의 합이된다. => 즉 dp[i][j..

1. 풀이 dp[i][j] : i번째 동전까지 사용해서 j원을 만들 수 있는 경우의 수. 기본적으로 무제한 동전dp(https://blog.naver.com/ngoodsamari/221664277387)와 같지만 사용할 수 있는 동전의 개수 제한이 추가된 문제이다. 무제한 동전 dp문제와 리스트형식은 같지만 푸는 방법이 전혀 다르다. ​ (1) 1번째부터 k번째까지 사용할 수 있는 동전을 하나씩 늘려간다 (2) i번쨰 동전을 사용할때는 i-1번째 동전까지 사용한 경우의 수에서 i번째 동전을 최대 사용가능한만큼 하나씩 늘려가며 확인한다. (3) i번째 동전까지 사용하여 0원을 만드는 경우는 1임을 주의한다. (무제한 동전dp와 같다) ​ 2.소스코드 T=int(input()) k=int(input()) L..

1. 풀이 처음엔 dfs만으로 완전탐색으로 문제를 풀었지만 시간초과. (소스코드1) 정답은 dp+dfs였다. 몇번을 풀었지만 어려운 dp & dfs문제.. ​ [원리] (1) 조건에 맞지 않으면 i. return 0으로 가지치기 (2) 조건에 맞으면 i. 끝까지가면 : return 1 ii. 방문한적이 있으면 return dp iii. 방문한적이 없으면 재귀후 저장 dp저장. 핵심은 바로 ii.방문한적이 있으면 return dp를 하는것! ​ ex) 4일동안 지각을 한번, 결석을 연속1번 한 경우를 생각해보자. 만약 이를 DFS+DP(소스코드1)로 푼다면, 해당 경우를 만족하는 모든 경우(OLOA,LOOA,OOLA)에 대해서 한번만 끝까지 계산을 해주고 DP에 저장해놓은다음, 다음에 만났을때 DP값을 반..

1.풀이 (1) 점화식 dp[i][j] : i개의 색 중 j개를 사용할 수 있는 경우의 수 (단 i dp[i][j]=dp[i-1][j]+dp[i-2][j-1] ​ dp[N][K] : N개의 색 중 K개를 사용할 수 있는 경우의 수. * i==N일때는 (원형이므로) 1번째 색깔이 칠해져있을때를 고려해주어야 한다. ㄱ. N-1번째까지 K개 사용한 경우 : dp[N-1][k] (i(=N)번째 색을 사용하지 않는 경우) : dp[N-1][K] ㄴ.1번째와 i-1번째가 색칠되어 있지 않는경우(i(=N)번째 색을 사용하는 경우) : dp[N-3][K-1] => dp[N][K]=dp[N-1][K]+dp[N-3][K-1] ​ (2) 초기조건 ㄱ. i개의 색 중 1개를 사용할 수 있는 경우는 항상 i개 ㄴ. i개의 색 ..

1.풀이 (1) 연속된 수의 합이므로 수열이 모두 양수라면 당연히 모든수를 다합하는것이 최대연속합이 된다. 하지만 음수가 있다면 달라진다. ​ (2) 점화식 (dp[i] : i번째 숫자를 포함하는 최대연속합) - 소스코드1 dp[i]=max(L[i],dp[i-1]+L[i]) - 소스코드2 그전까지 값(nowSum)이 음수이면 -> 이전값과 더하지 않고 새로시작 그전까지 값(nowSum)이 양수이면 -> 이전값과 더함 ​ 2.소스코드 (1) 소스코드1 n=int(input()) L=list(map(int,input().split())) dp=[0 for i in range(n)] nowSum=0 for i in range(n): nowSum=max(nowSum+L[i],L[i]) dp[i]=nowSum p..

1.풀이 N보다 작은 수들을 가지고 dp[N]를 만들 수 있는 방법은 다음과 같다 ​ (N-1^2) + 1^2 (N-2^2) + 2^2 (N-3^2) + 3^2 . . . ​ 따라서 dp[N]을 자연수 N의 최소 제곱수의 개수라고 할때 점화식을 dp[N]=min(dp[N-1^2],dp[N-2^2],dp[N-3^2]...)+1로 나타낼 수 있다. ​ 2.소스코드 import math INF=9876543210 N=int(input()) dp=[i for i in range(N+1)] dp[0]=0 for i in range(1,N+1): j=1 while(1): power=j**2 if i

1.풀이 처음에는 0부터 N까지 올라가는 bottom up 방식으로 쉽게 풀려고 했다. 하지만 N의 범위가 최대 10^12 이기 때문에 P,Q와 관계없이 무조건 시간초과 메모리초과다. ​(소스코드1) ​ 올바른 풀이는 다음과 같다. (소스코드2) (1) top down방식으로 dp를 풀어야 한다. N에서 시작하여 P,Q로 쪼개가면서 탐색한다. (2) 이때 한번 탐색한 곳은 저장해놓는다 (dp) (3) 하지만 N의 범위가 10^12 이기 때문에 배열로는 메모리 초과가 난다. 따라서 dictionary 자료형을 써야한다. 새로운 유형의 dp였다. ​ 2. 소스코드1 (1) 소스코드1 (bottom up, 메모리초과, 시간초과) N,P,Q=map(int,input().split()) dp=[1 for i in..

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. 풀이 (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..

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