반응형

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

 

17218번: 비밀번호 만들기

첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열 str1, str2를 입력받습니다.

 

2. str1[ i ] 와 str2[ j ]가 일치할 때 arr[ i ][ j ] = arr[ i - 1 ][ j - 1 ]  + 1의 점화식을 통해 최댓값을 ans에 저장합니다.

 

3. dp의 끝부터 분기를 통해 공통부분 문자열이 증가했을 때 ans에 해당 문자를 넣습니다.

 

4. 공통 부분 문자열을 출력합니다.

 

[ 소스코드 ]

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<string>
 
using namespace std;
 
string str1, str2;
int dp[41][41];
 
int main()
{
    cin >> str1 >> str2;
 
    for (int i = 1; i <= str1.size(); i++) {
        for (int j = 1; j <= str2.size(); j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
 
    int i = str1.size();
    int j = str2.size();
    string ans;
 
    while (1) {
        if (dp[i][j - 1] == dp[i][j] - 1 && dp[i - 1][j] == dp[i][j] - 1 && dp[i-1][j-1] == dp[i][j]-1) {
            ans = str1[i - 1] + ans;
            i--;
            j--;
        }
        else if (dp[i][j - 1] == dp[i][j] - 1 && dp[i - 1][j] == dp[i][j]) {
            i--;
        }
        else if (dp[i][j - 1] == dp[i][j] && dp[i - 1][j] == dp[i][j] - 1) {
            j--;
        }
        else {
            i--;
            j--;
        }
 
        if (i == 0 || j == 0) break;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 9370번 - 미확인 도착지 (C++)  (0) 2023.04.26
[ 백준 ] 2671번 - 잠수함식별 (C++)  (0) 2023.04.25
[ 백준 ] 6987번 - 월드컵 (C++)  (0) 2023.04.23
[ 백준 ] 11000번 - 강의실 배정 (C++)  (0) 2023.04.22
[ 백준 ] 20311번 - 화학 실험 (C++)  (0) 2023.04.21

+ Recent posts

티스토리툴바