[백준] 2661번: 좋은 수열

🛠️ 문제 

2661번: 좋은 수열

 

 

💡 풀이

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim();


const n = parseInt(input, 10); 

function isValid(sequence) {
    const len = sequence.length;

    // 같은 숫자가 3번 이상 연속인지 확인
    if (len >= 3 && sequence[len - 1] === sequence[len - 2] && sequence[len - 2] === sequence[len - 3]) {
        return false;
    }

    // 부분 수열 중 1, 2, 3이 연속인지 확인
    if (len >= 3) {
        const lastThree = sequence.slice(-3);
        if (lastThree[0] !== lastThree[1] && lastThree[1] !== lastThree[2] && lastThree[0] !== lastThree[2]) {
            return false;
        }
    }

    return true;
}

function findGoodSequence(n, sequence = []) {
    if (sequence.length === n) {
        return sequence.join('');
    }

    for (let i = 1; i <= 3; i++) {
        sequence.push(i);
        if (isValid(sequence)) {
            const result = findGoodSequence(n, sequence);
            if (result) {
                return result;
            }
        }
        sequence.pop();
    }

    return null;
}

console.log(findGoodSequence(n));

 

 

Algorithm-study/Algorithm/Solving/Backtracking/2661.js at main · kwonboryong/Algorithm-study

3주차 - 6일 | Notion