[백준 알고리즘][백트래킹] 2661번 좋은수열

문제

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열 1213121이다.

입력과 출력 

입력은 숫자 N하나로 이루어진다. (1<=N<=80) 출력은 1,2,3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

풀이

1, 2, 3만으로 길이가 N이 되는 숫자를 만들어야한다. 가장 작은 수를 나타내도록 하는 부분은 길이가 N되는 수열을 만들었을 때 min값을 결과값으로 계속 가져있게 해주도록 변수를 만든다. 중요한 나쁜 수열을 판단하기위해서는... 1,2,3으로 길이가 N이 되도록 수열을 만들고 모든 경우에 대해서 임의의 길이의 인접한 두 개의 부분 수열이 동일한 지, 아닌지를 판단해야하는 것 같다. 

근데 그럼 너무 비효율적인것같은데.. 동일한 부분 수열이 존재하는지를 쉽게 알려면 어떻게 해야할까.. 지금 생각나는 방법은 길이가 N인 수열에서 비교해야하는 부분 수열의 길이는 1~N/2 만큼이다. 그러면 1에서 N/2에 대해 부분 수열을 만들어서 해당 부분 수열이 존재하는 지를 체크하고 1보다 큰 경우가 생기면 나쁜 수열로 판단한다. 아 근데 인접해서 있어야 하는 구나..! 1에서 N/2까지의 길이를 가진 부분 수열이 존재하는지 확인 후, 그 다음에 바로 나타나는지 아닌지 보면 되겠다.

근데 생각해보니까 이 문제를 백트래킹으로 풀어야겠다고 시작했는데 그냥 무식하게 풀고 있는 것 같다.. 부분 수열이 존재하는지를 볼 길이가 N이 되는 수열을 어떻게 만들어낼지가 안 떠오른다. 백트래킹을 굳이 막 넣어서 생각을 해보자면 길이가 N이 되는 수열을 만들다가 만약 만드는 도중에 부분 수열이 생기면 바로 다시 돌아가서 새로운 시도를 하는 것이다. 즉 promising 한지를 보는 것이 부분 수열이 있는지를 보고 없을 경우에만 계속 모든 경우를 시도해야한다. 이렇게 풀면될 것 같다. 근데 이제는 1~N/2의 길이를 가지는 부분 수열을 어떻게 구해서 저장해둘지가 고민이다. 아니다 저장을 안해도 되겠다! 길이가 N이 되도록 만들때까지 계속해서 반으로 쪼개고 1에서 절반되는 길이까지의 부분 수열들이 어떤게 있는지 그 안에서 promising 유무를 봐야겠다.

* 어제 하루종일 푸는데 길이를 7로 입력해도 4까지만 만들어지다가 종료되어버리고 했는데 for문에 조건이 이상하게 되어있었다 파라매터로 받은 length를 기준으로 해야하는데 모르고 N 기준으로 해버렸다... promising 한 부분은 다 고친 것 같은데 백준 온라인 저지에서는 틀렸습니다가 뜬다 ㅠㅠ string으로 수열을 출력해서 문제인가싶어서 int형으로도 출력해봤는데... 아직 틀렸습니다 뜬다.

+추가 2018.11.12

이런 문제는 쉬우면서도 은근 접근을 잘못하면 어려운 것 같다! 부분수열 존재검사만 잘 짜면 되는 문제다. 처음 for문을 3개를 엉망으로 만들어버렸었다. 비교할 문자열의 size를 늘려가면서 i, j, k를 적절하게 해주면 된다. 전에 짰던 코드에서는 for문의 반복조건이 k++이어야 하는데 k=k+i라는 부분이 있어서 틀린거였다. 그리고 이번에 짜면서는 backtracking할 때 당연히 같은 자리에 다른 숫자로 덮히니까 '0' 으로 바꾸는 작업을 안했는데 그거 때문에 틀린거였다. 거꾸로 돌아갈 때 값을 초기화해주니 맞았다.

코드

#include<iostream>

using namespace std;

int N;

char result[81];

int check(int size);

int found;

void back(int size){

   if(found == 1)

      return ;

   if(size == N){

      cout<<result<<endl;

      found = 1;

      return ;

   }

   for(int i=1; i<=3 ; i++){

      result[size] = i + '0';

      if(check(size))

         back(size+1);

      result[size] = '0';

   }

}

int check(int size){

   int cnt;

   int half = (size+1)/2; //size는 0부터 시작한 숫자의 크기이므로 길이에 사용하려면 +1 해줘야함

   

   for(int i=1; i<=half; i++){

      for(int j=0; j<=size-i; j++){

         cnt=0;

         for(int z=j, k=j+i; z<j+i; z++, k++){

            if(result[z] == result[k]){

               cnt++;   

            }

         }

         if(cnt == i){

            return 0;

         }

      }

   }   

   return 1;

}

int main(){

   cin>>N;

   

   found = 0;

   back(0);

   

   return 0;

}