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




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
 
#define max(a,b) a>b ? a:b
 
int main() {
    char arr[1001];
    char arr1[1001];
    int dp[1001][1001] = { 0, };
    
    scanf("%s %s", &arr, &arr1);
 
    int a = strlen(arr);
    int b = strlen(arr1);
    
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            if (arr[i - 1] == arr1[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);        
        }
    }
    
    printf("%d", dp[a][b]);
    
    return 0;
}
cs


'알고리즘' 카테고리의 다른 글

(11055)(DP) 백준 가장 큰 증가 부분 수열  (0) 2018.08.07
(2133)(DP) 백준 타일 채우기  (2) 2018.08.06
(1699)(DP) 백준 제곱수의 합  (0) 2018.08.04
(11048)(DP) 백준 이동하기  (0) 2018.08.01
(2294)(DP) 백준 동전2  (0) 2018.08.01

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 값을 지속적으로 비교해서 저장해 주면 끝이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
#define max(a,b) a>b ? a:b
 
int main() {
    int N;
    int arr[1001] = { 0 };
    int dp[1001] = { 0 };
    int cnt;
 
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    dp[1] = arr[1];
    cnt = arr[1];
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + arr[i]);
            if (dp[i] == 0) dp[i] = arr[i];
        }
        cnt = max(cnt, dp[i]);
    }
 
    printf("%d", cnt);
 
    return 0;
}
cs


'알고리즘' 카테고리의 다른 글

(9251)(DP) 백준 LCS  (0) 2018.08.10
(2133)(DP) 백준 타일 채우기  (2) 2018.08.06
(1699)(DP) 백준 제곱수의 합  (0) 2018.08.04
(11048)(DP) 백준 이동하기  (0) 2018.08.01
(2294)(DP) 백준 동전2  (0) 2018.08.01

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  이 성립하게 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int main() {
    int N;
    int dp[31] = { 0 };
 
    scanf("%d", &N);
 
    dp[0] = 1;
    dp[2] = 3;
 
    for (int i = 4; i <= N; i+=2) {
        dp[i] = dp[i - 2] * 3;
        for (int j = 4; j <= i; j += 2) {
            dp[i] += dp[i - j] * 2;
        }
    }
 
    printf("%d\n", dp[N]);
 
    return 0;
}
cs



'알고리즘' 카테고리의 다른 글

(9251)(DP) 백준 LCS  (0) 2018.08.10
(11055)(DP) 백준 가장 큰 증가 부분 수열  (0) 2018.08.07
(1699)(DP) 백준 제곱수의 합  (0) 2018.08.04
(11048)(DP) 백준 이동하기  (0) 2018.08.01
(2294)(DP) 백준 동전2  (0) 2018.08.01

+ Recent posts

티스토리툴바