소프티어

2가지로 풀어봤습니다.

1번 코드입니다.

// 입력처리
const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8')
    .trim()
    .split('\n')
const [n, m] = input[0].split(' ').map(Number);
const nucleicSequences = input.slice(1).map(nucleicSequence => nucleicSequence.split(''))
// 비트 마스킹을 위한 0 채우기
nucleicSequences.unshift(-1)


//console.log(n, m)
//console.log(nucleicSequences)




// Sequence 가 1 ~ 5 존재한다고 가정
// Sequence 3에 그룹 1은 Sequence 1 ~ 2 까지가 동일한 염기를 공유하는 그룹 1 인 것.
// 따라서 Sequence 3 에서도 최소한의 그룹으로 분리가 되어야 함. 만약 a a b * * * * * 이렇게 나온다면, 2개의 그룹으로 분리되는 것이 최적. Sequence 3 부터 그룹 1 은 2개의 슈퍼 염기서열로 분화된다는 것
// 그렇다면 와일드 카드는 a, b로 분화되어 가야함. 당연히 이후 Sequence 에 대해서 고려하는건 불가능하니 전부 다 하기
// 하지만 1 - s 은 하나의 그룹, s - n 은 이후 s 가 n 까지 진행하면 몇 개의 그룹으로 분화하는지를 나타냄. 그렇다면 s 이후의 m - n 은? m 에 대한 그룹 1 개가 이후 분화를 진행하면 나오는 결과를 가지고 있다고 보면 됨.
// 띠라서 sequence 마다 각 그룹이 탐색을 마치면 그걸 기록 해야 함. 해당 sequence 에 있는 특정 그룹은 이미 진행된 결과, ? 한 개수를 반환하다. 이렇게


const cache = Array.from({ length: m }, () => ({}))
const cache2 = {}


function BitToIndexes(bit) {
    if (cache2[bit]) {
        return cache2[bit]
    }


    let index = 1
    const indexes = []
    const originBit = bit
    while (bit > 0) {
        if ((bit & 1) === 1) {
            indexes.push(index)
        }
        index++
        bit >>= 1
    }
    cache2[originBit] = indexes
    return indexes
}


function IndexToBit(index) {
    return 1 << (index - 1);
}




let rootMin = Number.MAX_SAFE_INTEGER


function DP(groupIdsBit, sequence) {
    // groupIds 를 읽어서 염기별 구분
    const nucleicObj = {
        a: 0,
        c: 0,
        g: 0,
        t: 0,
        '.': 0
    }


    const groupIdsIndex = BitToIndexes(groupIdsBit)


    groupIdsIndex.forEach(id => {
        const nucleic = nucleicSequences[id][sequence]
        const bit = IndexToBit(id)
        nucleicObj[nucleic] |= bit
    })


    // 현재 등록된 염기
    const currentNucleic = []
    for (let key in nucleicObj) {
        if (nucleicObj[key] >= 1 && key !== '.') currentNucleic.push(key);
    }


    // s 마지막
    if (sequence === (m-1)) {
        // 일반 염기 개수 or 와이들 카드 1개
        return currentNucleic.length !== 0 ? currentNucleic.length : 1
    }


    // 전부 염기서열이 와일드 카드 인 경우
    if (currentNucleic.length === 0) {
        // 현재 염기가 없다 => 전부 와일드 카드로 되어 있다.
        // 그대로 넘겨준다
        if (cache[sequence][groupIdsBit]) {
            return cache[sequence][groupIdsBit]
        } else {
            const t2 = DP(groupIdsBit, sequence + 1)
            cache[sequence][groupIdsBit] = t2
            return t2


        }
    }


    // 와일드 카드 분화
    const wildIdsIndexes = BitToIndexes(nucleicObj['.'])
    const wildList = Array(wildIdsIndexes.length).fill(0)


    let min = Number.MAX_SAFE_INTEGER


    const t = Math.pow(currentNucleic.length, wildList.length)
    // 와일드 카드 분화
    for (let i = 0; i < t; i++) {
        // 와일드 카드를 통해 새로 obj
        let count = 0
        let tempObj = {...nucleicObj}
        wildList.forEach((currentNucleicIndex, wildIdsIndexesIndex) => {
            const nucleic = currentNucleic[currentNucleicIndex]
            const wildIdIndex = wildIdsIndexes[wildIdsIndexesIndex]
            const wildId = IndexToBit(wildIdIndex)
            tempObj[nucleic] |= wildId
        })


        // 새 obj 기준 dp 시작
        //console.log("탐색 시작")
        //console.log(sequence, nucleicObj)
        for (let nucleic of currentNucleic) {
            const newGroupIds = wildList.length === 0 ? nucleicObj[nucleic] : tempObj[nucleic]
            if (cache[sequence][newGroupIds]) {
                count += cache[sequence][newGroupIds]
            } else {
                const t2 = DP(newGroupIds, sequence + 1)
                cache[sequence][newGroupIds] = t2
                count += t2
            }


            //console.log("결과")
            //console.log(sequence, nucleic, nucleicObj, wildList.length === 0 ? nucleicObj : tempObj, count)
            // 계산 도중 값이 현재 기준 최솟값보다 크면, 더 이상 의미 없으니 바로 탈출
            if (count >= rootMin) {
                break;
            }
        }


        min = Math.min(min, count)
        if (sequence === 0) {
            rootMin = min
        }
        //console.log(min, count)


        // add 연산
        for (let j = 0; j < wildList.length; j++) {
            // carry 발생
            if (wildList[j] === (currentNucleic.length - 1)) {
                // 그냥 pass
                wildList[j] = 0
                continue
            }
            wildList[j] += 1
            break
        }
    }


    //cache[sequence][groupIdsBit] = min
    return min
}


//console.log(Math.pow(2, n) - 1)
const a = DP(Math.pow(2, n) - 1, 0)
console.log(a)

설계 배경은

모든 유전자를 1번 순서부터 m까지 읽어나가는 도중에 유전자 그룹이 얼마나 많이 분열되는지 측정하는 겁니다.

aa

ab

cc

라는 유전자가 있으면

1번을 읽으면 a,c라는 2개의 그룹으로 나뉘고 각자 비트마스킹으로 그룹화해서 DP를 합니다.

이어서 2번을 읽으면, 기준 aa그룹에서 a,b로 나뉘게 되며 최종적으로 3개의 그룹으로 DP는 return하게 됩니다.

이 코드가 100점으로 처리되지는 않았지만, 오답이라고 뜨지 않은 것을 보면 답은 맞게 나오는 것 같습니다.

하지만, 시간 초과가 존재했고. 12개 -> 11 -> 1 줄여보았지만, 뭘해도 53번 테스트 케이스에서는 계속 시간 초과가 나왔기에 새로운 코드 설계를 해보았습니다.

2번 코드입니다.

// 입력처리
const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8')
    .trim()
    .split('\n')
const [n, m] = input[0].split(' ').map(Number);
const nucleicSequences = input.slice(1).map(nucleicSequence => nucleicSequence.split(''))

// 비트 마스킹을 위한 0 채우기
nucleicSequences.unshift(-1)

let oneSuperGeneGroups = {
    0: Array.from({ length: m }, () => '.')
}
const oneSuperGeneSave = {}

function indexToBit(index) {
    return 1 << (index - 1);
}

function merge(dna1, dna2, newOneSuperGeneGroups, newBit) {
    const newDna = []
    for (let i = 0; i < m; i++) {
        // 서로 같으면
        if (dna1[i] === dna2[i]) {
            newDna[i] = dna2[i]
        }
        // 둘 중 하나가 와일드 카드 이면
        else if (dna1[i] === '.' || dna2[i] === '.') {
            // 1이 와일드 카드이면 2의 값을 넣으면 됨
            if (dna1[i] === '.') {
                newDna[i] = dna2[i]
            }
            // 아니면 1의 값
            else {
                newDna[i] = dna1[i]
            }
        }
        // 전혀 다르면
        else {
            // 기존 슈퍼 dna를 기록해놓기
            return 1
        }
    }
    // 새로 합쳐진 슈퍼 유전자 추가
    newOneSuperGeneGroups[newBit] = newDna
    return 0
}

for (let geneCount = 1; geneCount <= n; geneCount++) {
    // 합침 대기중인 슈퍼 유전자
    const newOneSuperGeneGroups = {}
    Object.keys(oneSuperGeneGroups).forEach(selectedBit => {
        const oneSuperGene = oneSuperGeneGroups[selectedBit]

        // 해당 슈퍼 유전자가 한번도 다른 유전자를 포용할 수 있는지 없는지
        let count = 0

        // 처음 유전자들 순회
        for (let index = 1; index <= n; index++) {
            const newBit = selectedBit | indexToBit(index)
            let result = 1
            // 이미 그룹된 유전자들 이라면, 재반복하지 않고 처리했다고 기록
            if (newBit in newOneSuperGeneGroups) {
                result = 0
            }
            // 기존 선택된 유전자 그롭과 새로 선택된 유전자 그룹의 차이가 존재해야만 진행
            else if (selectedBit - newBit !== 0) {
                result = merge(oneSuperGene, nucleicSequences[index], newOneSuperGeneGroups, newBit);
            }
            count += result

        }
        if (count === n) {
            // 기존 유전자를 돌면서 기존 슈퍼 유전자에서 파생이 전혀 생기지 않았으면, 추출하고 따로 저장
            oneSuperGeneSave[selectedBit] = oneSuperGene
        }
    })
    // 요소가 + 1 된 슈퍼 유전자 그룹으로 변경
    oneSuperGeneGroups = newOneSuperGeneGroups
}

// 하나도 저장된 것이 없다는 것 => 조합할때마다 항상 새로운 유전자가 포함되었다는 것
if (Object.keys(oneSuperGeneSave).length === 0) {
    console.log(1)
    return
}

//console.log('추출된 1개의 슈퍼 유전자들의 최대 그룹')
//console.log(oneSuperGeneSave)
let superGeneSave = oneSuperGeneSave
const oneSuperKeys = Object.keys(oneSuperGeneSave)
const pow = (1 << n) - 1

// 최소 1 ~ 최대 n 개로 모든 유전자들이 합쳐지는걸 고려
for (let i = 0; i < n; i++) {

    const newSuperGeneSave = {}
    const bits = Object.keys(superGeneSave)
    // 이거는 super 탐색
    for (let j = 0; j < bits.length; j++) {
        const super1Bit = bits[j]
        // 이거는 oneSuper 탐색
        for (let k = 0; k < oneSuperKeys.length; k++) {
            const super2Bit = oneSuperKeys[k]
            const newBit = super1Bit | super2Bit
            // 이미 선택되어 버린 유전자들이라면
            if (newBit in superGeneSave) {
                continue
            }
            else {
                newSuperGeneSave[newBit] = [...superGeneSave[super1Bit], oneSuperGeneSave[super2Bit]]
            }
            // 만일 모든 유전자를 포함하면
            if (newBit === pow) {
                // 현재 처리 중인
                //console.log(newSuperGeneSave)
                console.log(i + 2)
                return
            }

        }
    }
    superGeneSave = newSuperGeneSave
}

/*
1개의 슈퍼 염기 서열로 합쳐질 수 있는 그룹들을 만들어 낸다.
(1개의 슈퍼 염기 서열로 만족되는 그룹들의 부분 집합은 존재할 수 없다.)
해당 그룹의 염기 서열을 만족 시키기 위해서는 A라는 슈퍼 염기 서열이 필요하다는 것을 알게 된 것
(1 2 3 4) / (? 1 2) (3 4 ?) 이 될 수 도
쨋든 이 그룹들은 합치면 슈퍼 염기서열은 무조건 1개씩 늘어나게 되어있음. 안늘어나는것끼리는 이미 앞에서 진행했기에.
 */

/*
그렇게 n개의 슈퍼 유전자와 그들이 포함하는 염기서열 목록을 얻음
그럼 이걸 다시 진행하면됨.
2개로 묶고,
 */

이 코드는 풀이 영상을 참고하고 만들었습니다.

사실, 풀이영상 초반의 내용은 이해했는데, 후반의 내용은 이해가 안되어서 새로 알게된 접근 방법을 기반으로 저만의 방식대로 풀어보았습니다.

일단 유전자를 2개 끼리만 비교하고 3개 이상은 비교하지 않기로 했습니다. 그렇게 접근할꺼면 그냥 n개를 전부 비교하는거랑 다를게 없다고 보기에.

# 1

n개의 유전자를 가지는 슈퍼 유전자 그룹과 기존 1개의 유전자를 연속해서 합하며, 1개의 슈퍼 유전자로 만들 수 있는 최대의 그룹을 만들어냅니다.

그렇게 나온 1개 슈퍼유전자들은 서로 선택한 유전자들이 절대 부분집합으로 생성되지 않습니다.

1,3,5를 포함하는 슈퍼 유전자가 존재하면, 이것은 1,3 또는 3,5 를 기반으로 확장된 것이기에 최종적으로는 1,3,5만 존재하게 됩니다.

1,3,5, / 5, 7은 공존 가능합니다.

# 2

2번 과정은 1번 과정과 유사합니다.

그냥 슈퍼 유전자를 1+1 -> 2+1 -> 3+1을해서 늘리며 유전자 그룹을 늘리는겁니다.

아주 좋습니다.