[백준/C++] 2661번: 좋은수열(G4)

 

문제

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

2661번: 좋은수열

 

사용한 알고리즘

2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹

-> 백트래킹.
    모든 경우에 대해 따져주지 않아도 되는 가지치기 문제

 

 

풀이

나쁜 수열에는 마지막에 어떤 숫자를 추가하더라도 나쁜 수열이다.
따라서 우리는 좋은 수열들에 대해서만 추가적으로 숫자를 붙여가며 좋은 수열인지 테스트하면 된다.

 

*solve함수

1. 지금까지 만든 수열이 좋은 수열일 때만 숫자 하나를 붙여서 재귀함수를 수행한다.
   이때, 좋은 수열인지 판단하기 위해서는 check함수를 사용하였다.
2. 만든 수열의 길이가 n이 되면 그 수열을 출력 후 종료한다.

 

*check함수

현재 인덱스까지 좋은 수열이면 1을, 나쁜 수열이면 0을 반환하는 함수이다.

아래 수열 ans를 예로 들어보자.

idx	0	1	2	3	4	5	6
ans	1	2	3	2	1	2	3

반복문을 돌면서 뒤쪽부터 비교해준다.

i=1일 때 (인접한 길이 1의 부분 수열이 동일한지)
ans[6]==ans[5] ? 을 확인하고

i=2일 때 (인접한 길이 2의 부분 수열이 동일한지)
ans[6]==ans[4] && ans[5]==ans[3] ? 을 확인하고

i=3일 때 (인접한 길이 3의 부분 수열이 동일한지)
ans[6]==ans[3] && ans[5]==ans[2] && ans[4]==ans[1] ? 을 확인한다.

i=1부터 (idx+1)/2까지 전부 확인하였는데 동일한 부분 수열이 없었다면 1을 반환하면 된다.

 

 

 

소스코드

#include <iostream>

typedef long long ll;
using namespace std;
int ans[81];
int n;

int check(int idx){
    //현재 인덱스까지 좋은 수열이면 1을, 나쁜 수열이면 0을 반환하는 함수이다.

    //맨뒤부터 연속한 한글자가 같은지 두글자가 같은지...반반 같은지//를 체크한다.
    for(int i=1; i<=(idx+1)/2; i++){
        int same=1;
        for(int j=idx; j>idx-i; j--){
            if(ans[j]!=ans[j-i]){
                same=0;
                break;
            }
        }
        if(same) return 0;
    }
    return 1;
}
void solve(int idx){
    // 만든 수열의 길이가 n이 되면 그 수열을 출력 후 종료한다.
    if(idx==n){
        for(int i=0; i<n; i++) cout<<ans[i];
        exit(0);
    }
    for(int i=1; i<=3; i++){
        ans[idx]=i;
        if(check(idx)) // 지금까지 만든 수열이 좋은 수열일때만 숫자하나를 붙여서 재귀함수를 수행한다.
            solve(idx+1);
        else continue;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n;
    solve(0);

    return 0;
}