[백준 알고리즘] 2661번: 좋은수열
March 04, 2021
https://www.acmicpc.net/problem/2661
문제
문제
숫자 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들 사이에는 빈칸을 두지 않는다.
풀이
백트래킹으로 순열을 만들어내는 것은 어렵지 않았는데, 나쁜수열을 검사하는 로직이 쉽지 않았다. 처음에는 숫자가 1, 2, 3 중 하나이기 때문에 길이가 3인 부분수열이 연속되지 않게하면 전체에서도 연속되는 수열이 없을 것이라고 생각했는데, 잘못된 생각이었다.
부분수열을 체크하기 위해서는 연속될 수 있는 부분수열의 길이인 전체수열 / 2 보다 작은 길이를 가진 모든 부분수열을 체크해주어야 한다.
코드
' '
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int N;
string sequence = "";
bool isDup (string s){
int len = s.length();
int start = len - 1;
for (int i = 1; i <= len / 2; i++) { // 반복되는 부분수열이 될 수 있는 최대 길이
string first = s.substr(start - i, i); // 기준 부분수열을 하나씩 줄이면서
string second = s.substr(start, i); // 반복되는 부분수열이 있는지 검사한다.
if (first.compare(second) == 0) return true;
--start;
}
return false;
}
void search (int cnt){
if (cnt == N){
cout << sequence;
exit(0);
}
for (int i = 1 ; i <= 3 ; i++){
sequence.push_back('0' + i);
if(!isDup(sequence)){ // 나쁜 수열이 없을 때만 새로운 숫자를 추가한다.
search(cnt+1);
}
sequence.pop_back();
}
}
int main (){
cin >> N;
search(0);
}
