https://www.acmicpc.net/problem/2661
2661번: 좋은수열
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
www.acmicpc.net
🔔 문제 :
1 <= N <= 80 인 수 N 길이의 수열이 주어집니다
이 수열은 1 ,2, 3으로 이루어져있습니다.
임의의 길이가 인접한 두 개의 부분수열이 같으면 나쁜 수열입니다.
나쁜 수열이 아닌 좋은 수열의 최솟값을 구하는 문제입니다.
나쁜 수열)
1 1 (1 과 1이 같음)
1212 (12와 12가 같음)
좋은 수열)
13231
🔔 Kick Point :
DFS를 이용하여 수를 넣어보고 조건에 맞지 않을 시 백트래킹하여 뒤로 돌아와서 다시 수를 넣으면 되는 문제입니다.
여기서 한참 헤맨 부분이
isSame() 함수로 부분수열을 비교하는 함수입니다.
이때 int로만 하려니 너무 머리가 빠지겠더라구요.
다른 분들의 코드를 보니 string를 쓰시길래 저도 string을 이용해
부분수열을 넣고, substr로 비교하였습니다.
🔔 Code :
#include <iostream>
using namespace std;
int arr[80];
int n;
bool isSame(int diff, int end) {
string a;
for (int i = 0; i < end; i++) {
a.push_back(arr[i]);
}
for (int i = 0; i + diff * 2 <= end; i++) {
if (a.substr(i, diff) == a.substr(i + diff, diff)) return true;
}
return false;
}
bool check(int cnt) {
int end = cnt + 1;
// 1 ~ cnt/2 숫자 확인
for (int i = 1; i <= end/ 2; i++) {
if (isSame(i, end)) return false;
}
return true;
}
void DFS(int cnt) {
if (cnt == n) {
for (int i = 0; i < n; i++) {
cout << arr[i];
}
exit(0);
}
for (int i = 1; i < 4; i++) {
// 1, 2, 3 넣기
arr[cnt] = i;
// check() 함수
if (check(cnt)) DFS(cnt + 1);
}
}
int main() {
cin >> n;
DFS(0);
}