[C/C++] BOJ 2306 :: 유전자

BOJ 2306 :: 유전자

문제 링크 : https://www.acmicpc.net/problem/2306

처음에는 다이나믹 프로그래밍이니까 무조건 하나의 반복문 루프 안에서 끝내야 한다는 생각에 사로잡혀 한 번의 루프로 끝낼 수 있는 규칙을 찾지 못해 난관에 빠졌었다,

생각을 바로잡고 문제에 나와있는 규칙을 적용하여 재시도한 결과, 얼추 규칙에 맞는 프로그래밍을 할 수 있었다.

그러나 계속 틀렸습니다. 가 떠서 백준 슬랙을 통해 문의한 결과 ㅠㅠ 간과한 점을 알 수 있었다.

나는 2번 조건과 3번 조건을 각각의 반복문으로 진행시켜 주었는데 그러면 atat와 같은 KOI 유전자의 길이를 제대로 도출해낼 수 없었다.

따라서 같은 루프 안에서 2번 조건과 3번 조건을 함께 판단하는 것으로 코드를 변경함으로서 문제를 해결할 수 있었다.

나의 풀이

1. 단어의 길이 2부터 시작하여, 전체 길이까지 2차원 배열을 채워나간다.

2. KOI 유전자의 2번 조건을 판단한 후, dp배열을 갱신한다.

3. KOI 유전자의 3번 조건을 판단한 후, dp배열을 갱신한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/tree/master/Daliy_Algorithms/BOJ_2306

// 백준알고리즘 2306번 :: 유전자
#include<iostream>
#include<string>
using namespace std;
#define max(a,b) (a > b) ? a: b
 
char arr[502];
 
// dp[i][j] : i부터 j 인덱스의 문자열에서의 KOI 유전자 길이가 저장된 배열
int dp[502][502];
 
int main(void)
{
    string str;
    cin >> str;
 
    // 문자열의 길이
    int len = str.size();
 
    // 배열에 문자 저장
    for (int i = 0; i < len; i++)
        arr[i] = str[i];
 
    for (int size = 1; size < len; size++)
    {
        for (int start = 0; start + size < len; start++)
        {
            int end = start + size;
        
            // 어떤 X가 KOI 유전자라면, aXt와 gXc도 KOI 유전자이다.
            if ((arr[start] == 'a' && arr[end] == 't') || (arr[start] == 'g' && arr[end] == 'c'))
                dp[start][end] = dp[start+1][end - 1] + 2;
 
            // 어떤 X와 Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자이다.
            for (int mid = start; mid < end; mid++)
            {
                int v = dp[start][mid] + dp[mid + 1][end];
                dp[start][end] = max(dp[start][end], v);
            }
        }
    }
 
    cout << dp[0][len-1];
 
    return 0;
}