백준 2661번 좋은 수열
문제 해설
백트래킹 유형의 문제이다. 백트래킹으로 접근해보자.
백트래킹의 경우 조건이 중요하다. 여기선 좋은 수열이라는 조건이 존재한다.
따라서 길이가 n인 가능한 좋은 수열을 모두 찾는 것이다.
1. 좋은 수열 판단
어떻게 좋은 수열인지 판단할 수 있을까.
간단히 생각하면 나쁜 수열을 제거하면 좋은 수열이다.
직접 예시를 풀어보며 특성을 파악해보자.
숫자당 1칸이라고 생각하자.
- 33:
- 같은 숫자가 인접한다. => 나쁜 수열.
- 따라서 같은 숫자끼리는 인접하면 안된다.
- 32121323
먼저, 같은 숫자가 인접하는 경우는 없다.
두 칸씩 확인한다면, 첫 두 칸은 32, 두 번째 두 칸은 12로 다르다.
두 번째 숫자부터 두 칸씩 확인한다면 21, 다음 두 칸도 21이다.
이와 같이 하나씩 옮겨가면서 n칸씩 확인하면 좋은 수열인지 확인할 수 있다.
그렇다면 총 몇 칸까지 확인해야 할까.
간단히 생각하면 총 길이가 n이라면 n/2칸까지만 가능하다.
2. 백트래킹
이제 좋은 수열 판단은 가능하다.
그렇다면 가능한 좋은 수열의 모든 수를 확인해야 한다.
이는 재귀를 활용해 할 수 있다.
원하는 길이가 n일때
수열이 매개변수인 함수를 만든다.
- 수열의 길이가 n이 아니라면
- 매개변수 수열 뒤에 가능한 숫자를 추가하여 새로운 수열를 만든다.
- 새로운 수열이 좋은 수열인지 판단.
- 좋은 수열이라면 새로운 수열을 매개변수로 하여 재귀 호출
- 좋은 수열이 아니라면 pass
- 수열의 길이가 n이라면
- 이는 좋은 수열이다.
- 그러나 문제의 조건은 가장 작은 수열을 출력하는 것이다.
- 생각해보면 재귀 호출의 특성 상 가장 먼저 호출한 숫자가 제일 먼저 실행된다.
- 1, 2, 3을 순서대로 호출하면 1이 가장 먼저 도착할 것이다.
- 따라서 길이가 n인 수열 중 가장 먼저 도착한 것이 제일 작은 수열이다.
소스코드
#include <iostream>
#include <string>
// 백준 2661번 좋은 수열
using namespace std;
// 수열 만들기
// 좋은 수열만 확인
int n;
// 좋은 수열인지 확인
bool isGood(string val) {
// 1칸부터 n/2칸까지.
for (int i = 1; i <= val.length() / 2; i++) {
for (int j = 0; j < val.length()-i; j++) {
bool flag = true;
for (int k = j; k < j + i; k++) {
if (k + i > val.length())
break;
if (val[k] != val[k + i]) // 같지 않다면 좋은 수열
flag = false;
}
if (flag) // 나쁜 수열
return false;
}
}
return true;
}
void count(string val) {
if (val.length() == n) {
// 처음 도착하는 수가 제일 작은 수.
cout << val;
exit(0);
}
for (int i = 1; i <= 3; i++)
if (isGood(val + to_string(i)))
count(val + to_string(i));
return;
}
int main() {
cin >> n;
count("");
return 0;
}