oiehso0

https://www.acmicpc.net/problem/9251

풀이

1.    arr[i]와 arr[j]가 일치할 경우

dp[i][j] = dp[i - 1][j - 1] + 1;

2. 일치하지 않을경우 

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

그림 출처    :    https://m.blog.naver.com/PostView.nhn blogId=tjdwns0920&logNo=221129635977&targetKeyword=&targetRecommendationCode=1&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

https://www.acmicpc.net/problem/11055

풀이

이중 포문을 이용해서  

if(arr[i]> arr[j]) dp[i] = max(dp[i], dp[j] + arr[i]);

if(dp[i] == 0 ) dp[i] = arr[i];  하고 

max 값을 지속적으로 비교해서 저장해 주면 끝이다.

https://www.acmicpc.net/problem/2133

풀이

먼저 3xN 배열에서 N이 홀수일 경우는 2x1배열과  1x2배열의 조합으로는 채울 수 없다는 것을 알 수 있다.

그래서 3x2, 3x4, 3x6, 3x8 ....순서대로 배열을 채울 수 있는 경우의 수를 찾기로 한다.

3x2배열의 경우는 아래와 같이 3가지 경우의 수가 존재한다.  dp[2] = 3;

위의 모양을 조합해서 3x4의 배열을 채울 수 있는 경우는 3*3으로 9가지가 있는데 예외의 경우가 아래와 같이 2개 존재한다.

dp[4] = dp[2]*3 + 2(    그림 1)의 경우와 그림 2)의 경우   );

1)            ,       2)    

3x6의 배열은 

dp[6] = dp[4]*3 + dp[2]*2(위의 그림 1), 2)의 경우 2가지) + 2(    그림 3)의 경우와 그림 4)의 경우)

3)      ,    4)     

3x8의 배열은

dp[8] = dp[6]*3 + dp[4]*2 + dp[2]*2 + 2  이 성립하게 된다.

https://www.acmicpc.net/problem/1699

풀이

dp를 이용해서 풀기로 한다. N의 범위가 100,000이므로 100,000의 제곱근의 반올림 수인 317개의 배열을 선언해 주기로한다.

dp[100001] = { 0 };

arr[317]  = { 0 };

그리고 dp 배열을 모두 -1로 초기화 해주기로 한다. 그 이유는 0과 -1의 구분을 짓기 위해서인데 초기화 했던 -1로 계속 값이 남아 있는 경우는 이전까지의 

제곱수로 만들수 없다는 것을 의미하게끔 하기 위해 

또, dp[0]값과 초기화 값이 0으로 동일하다면 min함수를 쓰기가 어려워지기 때문에 if(dp == -1) 조건을 두어

사전에 거르기 위함이다.

dp[0] = 0개

dp[1] =   1개    /     1^2 

dp[2] =  2개    /   1^2 + 1^2 

dp[3] =   3개    /    1^2 + 1^2 + 1^2

dp[4] =    1개    /    min(dp[3] + 1개(1^2) or  dp[0] + 1개(2^2))

dp[5] =    2개   /    dp[4] + 1개(1^2)    

dp[6] =    3개    /    dp[5] + 1개(1^2)

dp[7] =     4개    /    dp[6] + 1개(1^2)

dp[8] =    2개    /    min(dp[7]    or   dp[4]  + 1개(2^2))

.

.

.

이런식으로 비교해주면서 최소값을 저장해 나가면 된다.

https://www.acmicpc.net/problem/11048

풀이

NxM의 배열을 받고 (1,1)부터 출발해서 (N,M)에 도착했을때 최대가 될 수 있게 사탕을 챙겨야한다.

이동할 수 있는 방법은     →    /    ↓    /    ↘︎    이렇게 세가지 방법이 있다. 하지만 여기서  사탕은 0보다 같거나 크기 때문에   ↘︎ 으로 갈때 ↓ 와 → or → 와 ↓ 조합으로 이동해도

적어도 손해는 없기 때문에 대각선 이동은 고려하지 않기로한다. 

(i,j) 까지 왔을때  최대값을 구하기 위해서는 (1,1)에서부터 끊임없이 비교를 하며 최대값을 채택해 (i,j)까지 와야한다.

예를 들어 (3,3)좌표에서 최대값을 가지고 싶을때  3,4번 화살표와 같이

(2,3)에서 와야하는지 (3,2)에서 와야하는지 비교가 필요하다.

즉, i 와 j 가 1 이 아닌 경우

arr[i][j] += max(arr[i][j-1], arr[i-1][j]); 와 같은 식이 성립한다.

그러면 나머지 두가지 경우가 남는다.

1. j == 1 인 경우

위 그림의 1번 화살표와 같이 비교할 필요없이 위에서 아래로 누적해주며 내려오면 된다.

if(j == 1) arr[i][j] += arr[i-1][j]; 

2. i == 1 인 경우

그림의 2번 화살표와 같이 오른쪽으로 누적해주기만 하면 되므로

if(i == 1) arr[i][j] += arr[i][j-1]; 과 같은 식이 성립한다. 

https://www.acmicpc.net/problem/2294

풀이

첫번째 줄에 n,k를 입력한다. n은 서로 다른 값의 동전의 종류이고 그 동전들을 적당히 이용해서 그 가치의 합을 k로 만들어야할때, 동전의 개수가 최소가 될때를 구해야한다.

단, 불가능한 경우에는 -1을 출력하기로 한다.

arr[101]을 0으로 초기화해주고 

dp[100001] 을 memset(dp, -1, sizeof(dp));를 이용해서 -1로 초기화 해주기로 한다. 

dp[0]은 0 으로 초기화

동전1 문제의 풀이법을 변형해서 dp[i] = dp[i - arr[j]] + 1; 을 사용하여 동전이 사용될 때마다 +1 을 누적하여 dp에 담기로 한다.

if( i >= arr[j] && dp[i - arr[j]] != -1)의 조건을 주어서 arr[j] 동전이 i의 값을 넘지 않고 dp[i - arr[j]]이 이전의 동전들의 값으로 만들 수 있는 경우만 생각하면 된다.

하지만 dp[i] == -1 인 경우는 dp[i]가 처음으로 -1에서 값을 가지는 순간이므로 min함수로 비교를 하지않고 바로 dp[i] = dp[i - arr[j]] +1; 이 된다.  이 다음부터는

dp[i] = min(dp[i], dp[i - arr[j]] + 1);로 매번 비교를 해주어야 한다.

https://www.acmicpc.net/problem/11057

풀이

https://www.acmicpc.net/problem/2167

풀이

문제 설명이 구체적으로 되어있지 않아서 헤맸다.

ex)

arr[1][1]    arr[1][2]    arr[1][3]    arr[1][4]

arr[2][1]    arr[2][2]    arr[2][3]    arr[2][4]

arr[3][1]    arr[3][2]    arr[3][3]    arr[3][4]        와 같은 2차원 배열이 존재한다고 하고

문제를 이해하기로는 

i,j,x,y에 2,2,3,3을 주면

arr[1][1]    arr[1][2]    arr[1][3]    arr[1][4]

arr[2][1]    arr[2][2]    arr[2][3]    arr[2][4]

arr[3][1]    arr[3][2]    arr[3][3]    arr[3][4]    <-- 빨간 부분의 배열의 총 합을 구하는 거라고 생각했지만 X

arr[1][1]    arr[1][2]    arr[1][3]    arr[1][4]

arr[2][1]    arr[2][2]    arr[2][3]    arr[2][4]

arr[3][1]    arr[3][2]    arr[3][3]    arr[3][4]   <-- 이와 같이 사각형의 형태의 배열의 총 합을 구하는 문제였다.

그래서 나는 dp[i][j]를 이용해서 arr[1][1] 부터 arr[i][j]까지  총합을 구했다.

for (int i = 1; i <= N; i++) {

dp[i][1] = arr[i][1] + dp[i - 1][M];

for (int j = 2; j <= M; j++) {

dp[i][j] += dp[i][j-1] + arr[i][j];

}

}

그후에  x좌표의 값을 기준으로 for문을 이용해 이전에 구해 놓았던 dp값을 활용해서 한줄씩 부분 배열의 합을 구하기로 한다.

for (int i = 1; i <= T; i++) {

scanf("%d %d %d %d", &a, &b, &x, &y);

for (a; a <= x; a++) {

r += dp[a][y] - dp[a][b]+ arr[a][b];

}

printf("%d\n", r);

r = 0;

}

https://www.acmicpc.net/problem/9461

풀이

파도반 수열은 피보나치 수열과 어느정도 닮은 부분이 있는데 삼각형을 나선으로 계속 추가하는데 가장 긴 변에 삼각형을 계속 추가한다. 이러한 특성 때문에 처음에

긴변이 생기기 전까지 변의 길이는 p(1)    =    p(2)    =    p(3)    =    1 로 동일하다.

초기 값을 제외하고 이후의 값들의 규칙을 찾아보면 

p[i]    =    p[i-1] + p[i-5]; 와 같은 형태를 띄는 것을 차례대로 삼각형을 추가하며 그려보면 어렵지 않게 알 수 있다.

또는 p[i]    =    p[n-2] + p[n-3];과 같은 규칙도 띈다.

https://www.acmicpc.net/problem/9465

풀이

2행 n열로 구성되어있는 스티커이기 때문에 2차원 배열을 이용해서 dp로 구하기로 한다.

dp[i][j] 는 arr[i][j]까지의 스티커 배열 중에 스티커를 골라 최대값이 나올 수 있게 골라 더한 값을 담는다고 하자.

i)

arr[1][1]    arr[1][2]   arr[1][3]    arr[1][4]    arr[1][5]

arr[2][1]   arr[2][2]    arr[2][3]    arr[2][4]    arr[2][5]            ===>    dp[1][4] = dp[2][2] + arr[1][4];

dp[2][4] = max(dp[1][2] + arr[2][4] , dp[1][3] + arr[2][4]); 

위와 같은 방법으로 모든 스티커에 대해 dp를 구해 나가고 마지막 배열 dp[1][N], dp[2][N] 두가지 값만 비교해서 최대값을 출력해주면 된다.