알고리즘 좋은수열(C++)

1027 : 좋은수열

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 564회    시도횟수: 1472회    Special Judge

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

 

다음은 나쁜 수열의 예이다. (밑줄 부분때문에 나쁜 수열이다.)
33
32121323
123123213

 

다음은 좋은 수열의 예이다.
2
32
32123
1232123

 

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라.

예를 들면 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열 1213121이다.

 

입력파일은 숫자 N 하나로 이루어진다.
N은 1 이상 80 이하이다.

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다.
수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

[Copy] 7

[Copy] 1213121

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

/**************************************************************     Problem: 1027     User: a132034     Language: C++     Result: Success     Time:0 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> #include    <string> using namespace std; bool isGoodSeq(); void dfs(int num, int N); bool fin = false; string res = ""; int main() {     int N;     cin >> N;       //첫 번째에는 무조건 1이 들어감.     dfs(1, N);     return 0;   } //좋은 수열인지 판단. bool isGoodSeq() {     //동일한 패턴이 있는지 체크.     for (int i = 2; i <= res.length() / 2; ++i){         //패턴은 1부터(사실상 1은 바로 전 것과 동일하지 않으면 되므로 2부터) 길이의 반 까지 비교         string pat1 = res.substr(res.length() - i, i); //비교할 패턴 1         string pat2 = res.substr(res.length() - i * 2, i); //비교할 패턴 2         if (pat1 == pat2){             res.erase(res.length() - 1);             return false;         }     }     return true; } void dfs(int num, int N) {     //첫 수열을 찾아낸 후에 그대로 모든 dfs를 끝내기 위함.     if (fin)         return;       //int to -> string     res += (num + '0');       if (!isGoodSeq())         return;       if (res.length() == N)     {         cout << res << endl;         fin = true;         return;     }       for (int i = 1; i <= 3; ++i)     {         if (i == num)             continue;         dfs(i, N); // 넣는다.     }     res.erase(res.length() - 1); // 뺀다. }

엄청 헤멨다. 숫자로 풀려고했는데 냥이 때문에 노트를 잘 못쓰다 보니... 생각만 하다 너무 복잡한 코드가 나와버렸다.

1. for (int j = 1; j <= (k + 1) / 2; ++j)
2.             {
3.                 bool flg = true;//일치하는 부분수열이 있는지 확인해 볼 벼수
4.                 //2.3..4.... (k+1)/N 까지 비교해봄
5.                 for (int idx = 0; idx < j; ++idx)
6.                 {
7.                     if (res[k - (j * 2) + idx + 1] != res[k - j + idx + 1]){ // 다를 경우 false가 된다.
8.                         flg = false;
9.                     }
10.                 }
11.                 if (flg == true)
12.                 {
13.                     //true를 유지한다는 것은 동일한 수열이라는 것.
14.                     ok = false;
15.                 }
16.             }

약간 이렇게.. 그래서 혹시 쉬운방법 없을까 하다가 

string을 사용하게 되었다. 사실 string은 자바에서 밖에 사용해본 적이 없어서 보통 string표현시에는 char*를 사용했었다. 

처음 사용해 보았는데 이것도 STL라이브러리에 있다. 

string을 include해주면 사용 가능.

다양한 기능이 있다.

여기에서는 erase, length, substr 정도를 사용하였다. 

insert, append, replace, find 등 뿐만 아니라 연산자도 사용 가능하다고 한다. 

실제로 사용한 함수 

1. erase(a,b)는 a번째부터 b개의 문자를 삭제하는 함수

2. length는 string의 길이를 리턴

3. substr(a,b)는 a번째부터 b개만큼의 문자를 string으로 리턴

좋은 수열 풀이 방법자체는 생각보다 크게 어렵지 않았다. (백트래킹)

푼 방법이 작은 수(1 -> 2 -> 3)부터 차례대로 체크하는 방법이라 처음 체크 완료된 수열이 가장 작은 수열이다. 

백트래킹 방법으로 풀었는데 dfs함수를 만들었다.

체크는 isGoodSeq함수를 이용했다. 

체크는 말그대로 중복된 수열이 있는지 체크하였다. 

체크는 길이 N의 수열을 기준으로 1부터 N/2까지의 길이를 체크해보면 된다. 

ex) 길이 9의 배열이 있을 경우 하나를 추가할 때. 

추가한 인덱스가 10일 때

1 2 3 4 5 6 7 8 9 10

9            와  10             비교 (길이가 1)

9 10        과  7 8            비교 (길이가 2)

8 9 10      과  5 6 7         비교 (길이가 3)

7 8 9 10    과  3 4 5 6      비교 (길이가 4)

6 7 8 9 10  과  1 2 3 4 5   비교 (길이가 5)

전부를 체크해 보면 된다. 

이중 하나라도 동일한 수열이 발견되면 10번째 인덱스에 추가하려던 숫자를 추가하지 않는다. 

fin 변수는 가장 처음 찾아낸 좋은 수열을 리턴하기 위해 만든 변수. 

만든 함수 자체가 처음 찾아낸 좋은 수열이 가장 작을 수 밖에 없기 때문에 (1부터 차례대로 추가하며 비교)

가장 처음 만든 함수가 좋은 수열이라면 그 후로는 fin을 true로 해 주어 모든 함수를 종료시킨다. 

for loop를 돌며 i와 num이 같은 경우 continue를 사용한 부분은

사실 isGoodSeq 함수에서 비교해줘야 할 길이 1일 때 중복되는 수열이 있는지 비교하는 부분인데

사실 이게 더 편해서 이렇게 하였다. 어떻게 해도 상관 없을 것 같다.

만약 이렇게 하고 싶지 않다면 continue 부분을 제외하고 isGoodSeq 함수 내에서 i의 시작을 1로 바꿔주면 된다.

마지막으로 res string에 숫자를 string으로 넣기 위해 '0'를 더했다. 

사실 아스키 코드 값에 따르면 48이라고 하는데 보기 좋으라고 '0'으로 했다. 숫자 48을 더해줘도 무방.

dfs의 마지막 for loop와 for loop가 끝난 후에 erase부분은 짝이다. 

대부분의 백트래킹 방법이 그렇듯 

추가 - 계산(종료시 리턴) - 제거 의 순서를 따라했다.