loltochess

N개의 카드를 갖기 위해 지불해야 하는 최솟값을 구하는 문제이다. 문제 해결 방법1. 카드의 개수에 따른 최솟값을 DP에 저장한다. 1개의 카드를 갖기 위해 지불해야 하는 최솟값을 구한다.2개의 카드를 갖기 위해 지불해야 하는 최솟값을 구한다....N개의 카드를 갖기 위해 지불해야하는 최솟값을 구한다. 카드의 개수가 늘어날수록 사용할 수 있는 카드의 종류가 늘어난다.종류가 늘어남에 따라 값이 감소하는지 관찰하고 감소한다면 갱신해준다.#include using namespace std;int arr[1001];int DP[1001];int main(void){ int a=0; cin>>a; for(int i=1; i>arr[i]; DP[i]=987654321; } for(int i=1; i=0) ..

N+1일 퇴사하기 전에 백준이가 얻을 수 있는 최대 이익을 출력하는 문제이다.익일을 기준으로 살펴보자. 만약 2일에 퇴사한다고 가정하자 그럼 1일에 있는 일은 3일이 소요되기 때문에 수행하지 못한다.만약 3일에 퇴사한다고 가정하자  그럼 1일에 있는 일은 3일이 소요되고 2일에 있는 일은 5일이 소요되기 때문에 아무런 일도 못한다.만약 4일에 퇴사한다고 가정하자 그럼 1일에 있는 일은 3일이 소요되기 때문에 (1일, 2일, 3일) 일하면 수행이 가능하다.2일에 있는 일은 5일이 소요되기 때문에 수행이 불가능하다. 3일에 있는 일은 1일이 소요되기 때문에 수행이 가능하다.(4일에 퇴사한다고 가정하면 1일에 있는 일을 하거나 3일에 있는 일을 하고 퇴사하면 된다.)만약 5일에 퇴사한다고 가정하자 일이 가능한..

길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력하는 문제이다. 문제 해결 방법1. 오르막 수의 길의 별로 오르막 수를 구한다. N이 1이면 총 오르막 개수는 총 10개이다. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 N이 2일 때 각 숫자별로 보겠다. 만약 00은 불가능하니 PASS01은 불가능 , 11은 가능 앞으로 앞이 0인 경우는 보지 않는다. 12, 22 가능 13, 23, 33 가능이런 느낌으로 자기보다 작은 이전 index의 숫자들을 탐색하면 된다. #include using namespace std;int DP[1001][10];int main(void){ int N=0; cin>>N; for(int i=0; i

문제 해결 방법1. 1부터 N까지 연산의 최솟값을 구한다.(DP배열)2.  N을 1로 만드는 방법을 위 값을 기반으로 찾는다. 2의 연산의 최솟값은 1이다.2에서는 2-1, 2/2만 가능하다 2/3은 불가능 3의 연산의 최솟값은 1이다.3에서는 3-1, 3/3이 가능한데 이 중 최솟값을 골라서 저장하면 되는 것이다. DP[1]DP[1]+1값을 저장한다.DP[3]=DP[1]+1 위 과정을 반복하면 DP배열은 이런 식으로 저장된다. N에서 1로 만드는 방법은 위 배열을 이용해서 거꾸로 가면 된다.10에서 보면 DP[10/3]은 불가능 DP[10/2]는 3의 연산 횟수 DP[10-1]은 2의 연산 횟수 결국 가장 작은 DP[9]가 선택된다. 이런 식으로 DP[1]까지 반복하면 된다.  #include usin..

#include using namespace std;int arr[1001];int DP[1001];int result[1001];int main(void){ int A=0; cin>>A; for(int i=0; i>arr[i]; } int max=0; int index=0; for(int i=0; iarr[j]&&DP[i]=0; i--) { if(DP[i]==max) { result[count]=arr[i]; count++; max--; } } for(int i=count-1; i>=0; i--) { cout 수열 A의 가장 긴 증가하는 부분 수열의 길이와 부분 수열을 출력하는 문제이다.증가하는 부분 수열의 길이는 쉽게 구할 수 있다.if(arr[i]>arr[j]&&DP[i]..

#include using namespace std;int arr[1001];int DP[1001];int main(void){ int A=0; cin>>A; for(int i=0; i>arr[i]; DP[i]=arr[i]; } int max=DP[0]; for(int i=0; iarr[j]&&DP[i]max) { max=DP[i]; } } } cout DP 배열에 지금까지 가능한 합을 저장한다.만약 arr[i]가 arr[j]보다 크다면  DP[i]와DP[j]+arr[i]를 비교한 후 DP[j]+arr[i]가 더 크다면 DP[i]값을 갱신.  max의 초기값은 DP[0]임에 주의하자.(왜?? for문 안에서 DP[0]에 대해 검사 안 함.)

#include using namespace std;int DP[1001];int DP2[1001];int arr[1001];int main(void){ int A=0; cin>>A; for(int i=0; i>arr[i]; } for(int i=0; iarr[j]&&DP[i]=0; i--) { for(int j=A-1; j>i; j--) { if(arr[i]>arr[j]&&DP2[i]max) { max=DP[i]+DP2[i]+1; } } cout가장 긴 바이토닉 수열을 찾아서 길이를 출력하는 문제이다. 바이토닉 수열이란 S1 2 k-1 k > Sk+1 > ... SN-1 > SN을 만족하는 수열을 의미한다. 예)1->2->5->4->2->1 1->2->55->3->1 문제 해결 ..

#include #include using namespace std;int DP[100001][3];int main(void){ int n=0; cin>>n; for(int i=0; i>DP[i][j]; } } int max1[3]={DP[0][0],DP[0][1],DP[0][2]}; int max2[3]={0}; int min1[3]={DP[0][0],DP[0][1],DP[0][2]}; int min2[3]={0}; for(int i=1; i-1) { max=max1[j-1]+DP[i][j]; } if(maxmin1[j-1]+DP[i][j]&&j-1>-1) { min=min1[j-1]+DP[i][j]; } if(min>min1[j]+DP[i][j]) { ..

#include using namespace std;int arr[1001];int DP[1001];int main(void){ int A=0; cin>>A; for(int i=0; i>arr[i]; } int max=0; for(int i=0; iarr[j]) { if(DP[i]max) { max=DP[i]; } } } } cout 가장 긴 증가하는 부분수열의 길이를 출력하는 것이 목표이다. 증가하는 부분수열이란??위 예제에서 가장 긴 증가하는 부분수열의  길이는 4이다.어떤 식으로 접근해야 할까??우선 입력값의 크기부터 살펴보자.입력값의 크기가 1000까지니까 for문을 두 번 사용해도 문제가 없다. for(int i=0; iarr[j]) { if(D..

#include using namespace std;int DP[100001];int main(void){ int n=0; int k=0; cin>>n>>k; for(int i=1; i>w>>v; int temp[100001]={0}; for(int j=1; j=0) { if(temp[j-1]temp[j]) { temp[j]=DP[j]; } } for(int i=1; i 기본적인 배낭문제이다. 배낭에 가장 가치가 크게 물건을 야무지게 넣는 것이 목표이다. 무게를 기준으로 진행한다.i번째 물건이 들어왔을 때 가방의 무게를 1~k로 조절해서 물건을 최대한 넣는다.(가치가 가장 높게)푸는 방법1. 현재 가방 무게 - i번째 물건의 무게 >=0 즉 현재 가방에 i번째 물건을 ..