[Jungol] 정올 2217 DNA 조합

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1478&sca=3030

 Input 

4

GATTA

TAGG

ATCGA

CGCAT

 

 Output 

13

 

DNA 조각은 2  ≤ N  ≤ 7개가 있고 각 조각의 길이는 1  ≤ L  ≤ 7이다.

N개의 DNA조각을 임의의 순서로 나열해 인접한 두 DNA 조각에서

앞쪽 조각의 오른쪽 끝부분이 뒤쪽 조각의 왼쪽 끝부분과 최대한 많이 일치하는 부분을 찾고,

중복되는 부분을 제거한 후 나머지 부분을 순서대로 모아 새로운 DNA 조합을 만든다.

예를들어 GATTA + TACA = GATTACA

DFS를 이용한 백트래킹으로 두 문자열을 연결할 때 중복되는 문자의 개수를 구합니다.

DNA 조각의 개수가 최대 7개이므로 이때의 순서 조합은 7! = 5040가지이며,

모든 조합에 대한 길이를 구해서 최소값을 출력합니다.

 

두 문자열에서 겹치는 구간 찾기

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
inline int min(int x, int y) { return x < y ? x : y; }
int N, ans = 100, check[10];
char str[10][10];
int strlen(char*s, int len = 0) {
    while (s[len]) len++;
    return len;
}
 
int same(char a[], char b[]){
    int aLen = strlen(a), bLen = strlen(b);
    int pivot, left, right;
    // 가능한 최대 개수부터 확인
    for (pivot = min(aLen, bLen); pivot > 0; pivot--) { 
        // a의 접미사와 b의 접두사 i개 만큼 비교
        for (left = aLen - pivot, right = 0; left < aLen; left++, right++) 
            // 탐색 중간에 같지 않은 경우
            if (a[left] != b[right]) break;
        // 모두 같으면 b의 길이에서 i개를 뺀 길이 반환
        if (left == aLen) return bLen - pivot; 
    }
    // 공통된 부분이 없는 경우 b 문자열 길이 반환
    return bLen;
}
 
void DFS(int step, int idx, int len) {
    // 현재까지 선택된 개수, 현재 위치, 현재까지 길이
    if (len >= ans) return;
    if (step >= N) {
        // 모든 단어가 선택된 경우, 길이가 더 작기에 갱신
        ans = len;
        return;
    }
    // 순열
    for (int i = 1; i <= N; i++){
        if (check[i]) continue;
        check[i] = 1;
        DFS(step + 1, i, len + same(str[idx], str[i]));
        check[i] = 0;
    }
}
 
int main(){
    scanf("%d", &N);
    // str[0] = NULL;
    for (int i = 1; i <= N; i++)
        scanf("%s", str + i);
    DFS(0, 0, 0);
    printf("%d", ans);
}