BOJ : https://www.acmicpc.net/problem/3793

github : https://github.com/junho0956/Algorithm/blob/master/3793/3793/%EC%86%8C%EC%8A%A4.cpp

 

공통되는 최장 부분문자열인 LCS를 구하는 문제였습니다.

파일의 끝만 읽을줄 아는 방법과 LCS의 기본개념을 알고 계시면 문제를 해결할 수 있습니다.

 

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
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
 
int dp[201][201];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    string f, s;
 
    while (1) {
        cin >> f;
        if (cin.eof()) break;
        cin >> s;
 
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < f.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (f[i] == s[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
                else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
 
        cout << dp[f.length()][s.length()] << "\n";
    }
    
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 9251번 LCS  (0) 2020.02.12
BOJ 5502번 팰린드롬  (0) 2020.02.12
BOJ 1365번 꼬인 전깃줄  (0) 2020.02.11
BOJ 3745번 오름세  (0) 2020.02.11
BOJ 11568번 민균이의 계략  (0) 2020.02.11

BOJ : https://www.acmicpc.net/problem/1365

github : https://github.com/junho0956/Algorithm/blob/master/1365/1365/%EC%86%8C%EC%8A%A4.cpp

 

최대로 연결하기 위해서는 최소의 전선을 자르면 된다.

결국 가장 긴 부분수열의 값(lis)을 알고 있다면 전체값에서 빼주면 답이 된다.

 

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N;
vector<int> dp;
int arr[100001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    dp.push_back(arr[0]);
    int lis = 0;
 
    for (int i = 1; i < N; i++) {
        if (arr[i] > dp[lis]) {
            dp.push_back(arr[i]);
            lis++;
        }
        else {
            int lo = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
            dp[lo] = arr[i];
        }
    }
 
    cout << N-(lis + 1);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 5502번 팰린드롬  (0) 2020.02.12
BOJ 3793번 Common Subsequence  (0) 2020.02.12
BOJ 3745번 오름세  (0) 2020.02.11
BOJ 11568번 민균이의 계략  (0) 2020.02.11
BOJ 7570번 줄 세우기  (0) 2020.02.10

BOJ : https://www.acmicpc.net/problem/3745

github : https://github.com/junho0956/Algorithm/blob/master/3745/3745/%EC%86%8C%EC%8A%A4.cpp

 

dp의 한 종류인 lis 알고리즘과 파일의 끝을 판별하는 법을 사용할 줄 안다면 문제를 해결할 수 있습니다.

 

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
32
33
34
35
#include <cstdio>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
 
int N;
vector<int> dp;
int arr[100001];
 
int main() {
 
    while (scanf("%d", &N) != EOF) {
        for (int i = 0; i < N; i++) scanf("%d", &arr[i]);
        dp.clear();
 
        dp.push_back(arr[0]);
        int lis = 0;
 
        for (int i = 1; i < N; i++) {
            if (arr[i] > dp[lis]) {
                dp.push_back(arr[i]);
                lis++;
            }
            else {
                int lo = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
                dp[lo] = arr[i];
            }
        }
 
        printf("%d\n", lis + 1);
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 3793번 Common Subsequence  (0) 2020.02.12
BOJ 1365번 꼬인 전깃줄  (0) 2020.02.11
BOJ 11568번 민균이의 계략  (0) 2020.02.11
BOJ 7570번 줄 세우기  (0) 2020.02.10
BOJ 2631번 줄 세우기  (0) 2020.02.10

BOJ : https://www.acmicpc.net/problem/11568

github : https://github.com/junho0956/Algorithm/blob/master/11568/11568/%EC%86%8C%EC%8A%A4.cpp

 

일반적인 dp 중 한 부류인 lis 알고리즘으로 해결할 수 있습니다.

 

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N;
vector<int> dp;
int arr[1001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    dp.push_back(arr[0]);
    int lis = 0;
 
    for (int i = 1; i < N; i++) {
        if (arr[i] > dp[lis]) {
            dp.push_back(arr[i]);
            lis++;
        }
        else {
            int lo = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
            dp[lo] = arr[i];
        }
    }
 
    cout << lis + 1;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1365번 꼬인 전깃줄  (0) 2020.02.11
BOJ 3745번 오름세  (0) 2020.02.11
BOJ 7570번 줄 세우기  (0) 2020.02.10
BOJ 2631번 줄 세우기  (0) 2020.02.10
BOJ 2605번 줄 세우기  (0) 2020.02.10

+ Recent posts

티스토리툴바