| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1468 | 790 | 630 | 58.172% |
문제
숫자 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들 사이에는 빈칸을 두지 않는다.
예제 입력
7
예제 출력
1213121
힌트
> 풀이
백트래킹에 관련된 문제이다.
백트래킹은 dfs, bfs 와 유사하지만 조건이 맞지 않으면 바로 종료해서 속도를 높히는 기법이다.
이번 문제는 dfs 를 재귀함수로 구현하여 문제를 풀어보았다. (향후, 스택을 사용해서 문제를 풀어보아야 겠다. )
쉬워 보인다고 생각했는데, 삽질을 많이 하고 결국 문제 풀이를 구글링을 통해서 얻게 되었다. (dfs 방식은 생각했지만, 세밀한 구현 중의 오류나 시간 초과 같은 문제를 해결하지못했다. )
위와 같은 방식으로 깊이를 늘려가면서 깊이가 n이 되면 숫자가 규칙을 만족하는지 검사를 해주는 것이 dfs의 기본적인 원리이다.
하지만 이와 같은 방식으로 처리를 할 경우에는 시간 초과가 나오게 되었다.
왜냐하면 각 높이가 증가함에 따라서 자식이 3배씩 증가하게 되고, 마지막 단계에서 모든 숫자의 규칙을 검사하려면 아래와 같은 계산을 통해서 어마어마한 복잡도가 나오게 된다.
전체 시간 복잡도 : O(3n X n3)
n이 커지면 커질수록 기하 급수적으로 커지기 때문에 부적절한 설계였다.
그래서 규칙 검사를 각 단계마다 해주고 미리 탈락을 시키는 것으로 , 백트래킹이 dfs 가 전체를 탐색하는것과 비교하여 이전에 조건을 만족시키지 못하면 탈락시킨다는 점에 초점을 두고 생각해보았다.
이전 단계에서 규칙성을 만족했다면, 매 번 깊이가 증가할 때마다 규칙성 검사를 해서 탈락시키려면
끝에 자리 수를 기준으로 규칙 검사를 해주면 된다. (이전 자리 수는 전부 규칙을 만족하기 때문에)
위의 구조에서 규칙 계산 복잡도는 대략 O(n2) 라고 계산된다.
이는 n 이 최대 입력이 80 이기 때문에 무리가 없는 수치이다. ( 물론 n3 도 그렇지만, 위에서는 n3 보다 3n의 영향이 큰 것 같다.)
백트랙킹시 그래프의 모양은 아래와 같아지게 된다.
기존에 무조건 최고 깊이 까지 내려갔지만, 높이가 1이 되자 마자 바로 11에서 조건 체크를 해서 불만족임을 확인하고
버리기 때문에 엄청나게 수를 줄일 수 있다. 
자세한 시간 복잡도 계산은 추후 학습이 더 필요할 것 같다. (계산 되신 분은 좀 알려주세요 ㅜ)
>> 소스코드
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 70 71 72 | #include <algorithm> #include <iostream> #include <vector> #include <stdlib.h> using namespace std; int* num_array; int input_num = 0; int validation(int change_depth) { int same_num; //// validation check -> but this way is too late //for (int size = 1; size <= (input_num / 2); size++) { // // check one size number (from 1~ input/2 ) // for (int i = 0; i < input_num - 2 * size + 1; i++) { // same_num = 0; // // check one rule // for (int k = 0; k < size; k++) { // if (num_array[i + k] == num_array[i + k + size]) same_num++; // } // // if check and rule is fined , end function // if (same_num == size) return -1; // } //} // validation check -> when each round , we confirm that num is in rule for (int size = 1; size <= (change_depth / 2); size++) { same_num = 0; // check one rule for (int k = 0; k < size; k++) { if (num_array[(change_depth -1) - k] == num_array[(change_depth - 1) - k - size]) same_num++; } // if check and rule is fined , end function if (same_num == size) return -1; } // if it is ANSWER ? -> print and exit program. if (change_depth == input_num){ for (int i = 0; i < input_num; i++) { cout << num_array[i]; } exit(0); } return 1; } // confirm data and push answer into vector void confirm ( int change_depth) { if ( change_depth > input_num ) return; if ( validation(change_depth) == -1 ) return ; // check other numbers for (int i = 0; i < 3; i++) { num_array[change_depth] = i+1; confirm(change_depth + 1); } } int main() { cin >> input_num; num_array = (int*)malloc(sizeof(int)*input_num); // confirm array confirm(0); return 0; } | cs |