Hoon222y

https://www.acmicpc.net/problem/1328 이 또한 DP문제이다. N,L,R 이 주어졌을때 볼수 있는 가지수를 출력하는 문제이다. DP 테이블의 정의는 DP[i][j][k] = 빌딩이 i개 있을때 왼쪽으로 j개, 오른쪽으로 k개 가 보일때의 개수 라고 정의하고 문제를 접근할 수 있다. 해당 문제를 풀때 힌트라고 한다면 문제를 접근할때 2~n까지의 빌딩이 세워져 있다고 가정을 하고 높이 1의 건물을 넣을 수 있는 경우로 문제를 접근하면 좀 더 쉽게 풀 수 있다. 만약 높이기 1인 빌딩이 가장 왼쪽에 배열되게 된다면 dp[i][j][k] +=dp[i-1][j-1][k] 가 될것이고, 가장 오른쪽에 배열된다면 dp[i][j][k] += dp[i-1][j][k-1] 으로 생각할 수 있다...

https://www.acmicpc.net/problem/1495 DP문제이다. DP[i][j] 정의를 " i번째까지 사용하였을 때 j값을 만들수 있는가 없는가?" 로 정의하였다. 문제의 조건에 따라서 state값의 범위를 0이상 , m이하로 정의를 하고 pos가 n+1 까지 갔을때 state을 가지고 최대값을 가져왔다. 이번에도 재귀로 구현하였다. 근데 재귀 부분에서 ret = max(...) 이 부분 뭔가 깔끔하지가 않은데 이거 어케 해야될지 모르겠당 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include #include #inc..

https://www.acmicpc.net/problem/5557 DP문제이다. DP[i][j] 테이블 정의를 i번째 숫자까지 사용하였을 때 j가 나오는 경우의 수로 정의하면 dp[i][j] = dp[i-1][j-arr[i]]+dp[i-1][j+arr[i] 가 된다. 물론 조건인 0이상 20 이하를 if문으로 체크해주어야 한다. 27번째 줄처럼 가장 첫수의 가능 경우를 1로 설정해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include #include #include #include #include #define MAX_N 50#defin..

https://www.acmicpc.net/problem/1126 DP문제이다. 해당 문제의 경우 가능한 연산이 총 3가지이다.(1) 첫번째 블럭에 넣기 (큰쪽에 둔다는 의미)(2) 두번째 블럭에 넣기(3) 그냥 버리기 이 3가지 연산을 수행하게 되는데 두 블럭의 높이 차이를 기록하고 그 중 높은쪽을 생각하게 된다. 만약 n번째까지 다 쌓았을때 그 둘의 차이가 0이 되게 되면 두 블럭의 높이가 같다고 볼 수 있다. 문제의 조건에서 모든 블럭의 합이 50만을 넘지 않는다고 하였기 때문에 dp배열은 n*250000으로 생각할 수 있다. (3)번 연산은 36번째 줄 , (1)번 연산은 37번째 줄 , (2)번이 문제인데 만약 두려는 블럭의 크기가 두 블럭 사이의 높이 차 이상,이하일 때를 나누어서 생각해 볼 ..

https://www.acmicpc.net/problem/14501 예전에 모 기업 문제라고 올라왔던 문제이다. 그냥 간단한 DP인데 멍청하게도 갱신되는 구간을 전부다 확인하지 않는 삽질을 많이 했다. 점화식은 30~36을 참고하면 될것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #include #include #include #include #include #include #define MAX_N 10000typedef long long ll; using namespace std; int n,arr[3][111],dp[111]; int main(){..

https://www.acmicpc.net/problem/11058 해당 문제의 경우 DP로 접근을 한다. DP 테이블을 dp[i] = i번째 화면에 출력되는 최대 A의 개수 라고 정의를 한 다음 문제에 접근한다. 이 문제의 포인트는 1) i가 7을 넘어가면 버퍼에 있는 것을 복사하는 것이 최대가 된다.2) 정답은 int의 범위를 넘어간다는 것 (주의) 따라서 버퍼에 들어가기 위해서는 Ctrl +A, Ctrl + C, Ctrl + V 가 필수이므로 버퍼에 들어가는 경우의 점화식은 dp[i] = max(dp[i],dp[i-3]*2) 부터 시작하게 된다. 1234567891011121314151617181920212223242526272829303132333435#include #include #includ..

https://www.acmicpc.net/problem/2156일렬로 있는 포도주를 일정 규칙에 따라서 마실 때 최대로 마실 수 있는 양을 구하는 DP문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include using namespace std;int n;int dp[3][22222];int arr[22222];int main(){ memset(dp,0,sizeof(dp)); memset(arr,0,sizeof(arr)); scanf("%d" , &n); for(int i=1;i