[백준] 2661: 좋은 수열

0. 문제 주소

 

https://www.acmicpc.net/problem/2661

2661번: 좋은수열

 

 

1. 풀이

 

 

나쁜 수열을 어떻게 판별할까 고민했던 문제.

 

확실히 c++로 문자열을 처리하는 부분이 약한 걸 느꼈다.

 

 

마지막에 새로 추가하는 숫자를 포함하는 부분 수열만 체크할 것이고, 이 경우 체크해야 할 인접한 부분 수열의 길이는

 

1부터 (현재 문자열의 길이) / 2 까지 일 것이다.

 

그렇기에 부분 문자열의 길이를 i라 하고, 현재 문자열의 길이를 N이라고 한다면 비교해야 할 두 부분 수열은

 

1. (N - 2 x i) 부터 i개의 글자

2. (N - i) 부터 i개의 글자

 

일 것이다.

 

직접 인덱스를 이용해 순서대로 참조해가며 두 부분 수열에 속한 글자들이 일치한 횟수가 i와 같다면, 

 

나쁜 수열이 된다고 판단하는 방법도 있을 수 있다.

 

 

근데 그게 귀찮아서 찾아보니까 string 헤더에 substr 메소드가 있었다.

 

인자는 2개를 받는데, substr( i , n )이라고 하면 string의 i번째 index부터 n개의 글자만큼의 substring을 리턴해주는 메소드이다.

 

이걸 이용하여 모든 경우에 대하여 나쁜 수열이 되진 않는지 점검해주고, 이상이 없다면 다음 자리에 숫자를 추가해주며

 

백트래킹을 돌려주면 된다.

 

이 때 N 자리의 가장 작은 좋은 수열을 출력해야 하는데, 이를 위해선 맨 뒤에 추가할 숫자의 순서를

 

1에서 3까지로 정해주고, N 자리의 좋은 수열이 나오면 이를 바로 출력하고 exit(0)을 이용해 프로그램을 종료시키면 된다.

 

 

 

 

2. 풀이 코드

 

* 유의할 점

0. 매번 global에 bool 변수 succ를 추가해서 답을 찾았으면 true로 바꾸고, 다음 부터 succ이 true이면 바로 함수를

끝내는 방법을 썼는데... exit(0) 쓰면 되는 거였다.

1. 처음엔 수를 넣을 때마다 1 ~ 3 중에 하나는 무조건 추가할 수 있다고 생각하고 백트랙을 안 해주었다.

(bt 함수 맨 마지막 부분)

 

#include <bits/stdc++.h>

using namespace std;

int N;
string ans;

void bt(int len, char c)
{
    if (len == N + 1) {
        cout << ans << "\n";
        exit(0);
    }

    ans += c;

    for (int i=1;i<=len/2;i++){
        string a = ans.substr(len - 2*i, i);
        string b = ans.substr(len - i, i);

        if (a == b) {
            ans.erase(len - 1);
            return;
        }
    }

    for (int i=1;i<=3;i++){
        bt(len + 1, i + '0');
    }
    ans.erase(len-1);
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    cin >> N;

    bt(1, '1');
}