백준 2661 : 좋은 수열 - javascript(백트래킹)

문제 출처 

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

 

정답 풀이 

dfs 함수로 temp 배열을 채워나간다. 

그리고, 채워나갈 때 조건은 check 함수를 통해 좋은 수열인지 체크할 때의 값이 true 여야만 

다음 수를 채워나갈 수 있다. 

 

정답 코드 

//체크하는 함수 
//dfs로 123 계속 채우는 함수 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const n = Number(input[0]); 
function solution(n){
    let temp = new Array(n).fill(0)
    function dfs(L){
        if(L === n){
            console.log(temp.join(''))
            process.exit()
        }else{
            for(let i=1; i<=3; i++){
                temp[L] = i; 
              if(check(temp, L+1)){
                  dfs(L+1)
              }
            }
        }
    }
    dfs(0)
    
  function check(sequence, length){
      for (let i = 1; i <= Math.floor(length / 2); i++) {
            const sub1 = sequence.slice(length - i * 2, length - i).join('');
            const sub2 = sequence.slice(length - i, length).join('');
            if (sub1 === sub2) {
                return false;  
            }
        }
        return true;
    }
}

solution(n)

 

추가 설명

부분 수열을 확인할 때, 수열의 뒤에서부터만 i 길이의 부분 수열을 확인하는 이유는 문제에서 요구하는 "좋은 수열"의 정의와 관련이 있습니다.

1. 뒤에서부터 부분 수열을 확인하는 이유:

문제에서 좋은 수열이란 어떤 부분 수열도 반복되지 않는 수열을 의미합니다. 이때 반복이란, 같은 길이의 두 부분 수열이 서로 인접해서 동일하게 나타나는 경우를 말합니다. 즉, 수열의 끝부분에서 발생하는 반복만이 문제가 됩니다.

예를 들어, 수열 [1, 2, 1, 2]에서 마지막 두 개의 숫자 [1, 2]가 그 앞의 두 개의 숫자 [1, 2]와 동일하므로, 이 수열은 나쁜 수열입니다. 따라서, 수열의 끝부분에서 발생하는 부분 수열만 확인하면 됩니다.

더 구체적으로 말하자면, 우리는 수열의 끝부분이 그 이전과 동일하게 반복되는지 확인하는 것입니다. 예를 들어:

• 길이 4의 수열 [1, 2, 1, 2]에서 끝에서 2개의 숫자 [1, 2]는 그 앞의 2개의 숫자 [1, 2]와 동일하기 때문에, 이 수열은 나쁜 수열로 간주됩니다.

이것이 가능한 이유는, 만약 수열의 끝부분에서 반복이 발생하지 않으면 그보다 앞부분에서도 반복이 발생할 가능성이 없기 때문입니다. 끝부분에서 발생하지 않는다면, 그 앞부분에서의 반복은 수열의 성질상 더 작은 길이의 부분 수열일 것이고, 그 경우는 이미 검증된 상태가 됩니다.

2. 앞에서부터 확인하지 않아도 되는 이유:

수열의 시작 부분이나 중간 부분에서 발생하는 반복은 굳이 확인할 필요가 없습니다. 이는 수열이 만들어지면서 매 단계마다 좋은 수열인지 검증되기 때문에, 이전에 문제가 없었다면, 오직 마지막에 추가된 숫자로 인해 나쁜 수열이 발생할 수 있습니다.

다시 말해, 수열이 점차 확장되면서 뒤에 새로운 숫자가 추가될 때마다 그 부분에서 발생하는 반복만 확인해주면 충분합니다. 이전의 수열에 문제가 없었다면, 마지막에 추가된 숫자가 문제를 일으키는지 여부만 확인하면 되기 때문입니다.

예시:

javascript

코드 복사

sequence = [1, 2, 1, 2] length = 4

이 경우, i = 1일 때:

• sub1 = [2], sub2 = [2] → 동일하므로 계속 진행.

i = 2일 때:

• sub1 = [1, 2], sub2 = [1, 2] → 동일하므로 이 수열은 나쁜 수열로 간주됩니다.

결론:

뒤에서부터만 부분 수열을 확인해도 되는 이유는, 반복이 발생할 수 있는 가장 가능성이 큰 부분이 수열의 끝부분이며, 끝에서 발생하는 반복을 확인함으로써 나머지 수열의 유효성도 보장할 수 있기 때문입니다.