백준 2661번 : 좋은수열

문제 링크 : https://www.acmicpc.net/problem/2661

2661번: 좋은수열

 문제 설명  

 

숫자 1,2,3으로이루이저는 수열이있는데 인접한 두개의 수열이 똑같은 경우이 가있다면 나쁜수열이고 그런경우가 없다면 좋은 수열이다.

N이 주어졌을 때 길이 N의 좋은수열 중 가장 작은 값을 출력하시오 .

 

 알고리즘 

 

구현은 재귀로.

숫자를 하나 씩 추가할때마다 좋은수열인지 판별하고 좋은수열이아니면 return , 좋은 수열이면 숫자를 하나더추가 ... 반복

숫자를 1, 2,3 순으로 입력하면 자연스레 가장 낮은 값이 먼저 출력 된다.

출력이 이루어질 때 exit(0) 를통해 프로그램을 종료한다 .

 

좋은 수열 인지 판별법

만약 벡터의 크기가 8이다 그러면 (0 1 2 3)과 (4 5 6 7) 을 비교

그다음 (2 3 4)와 (5 6 7) 을 비교 -> (4 5),(6 7)비교 -> (6) (7) 비교 이런식으로비교 하면서 좋은수열을 판별한다 .

 

 코드 

 

#include<iostream>
#include<vector>
using namespace std;
 
int N;
 
//좋은 수열 판별
bool good(vector<int> v) {
    int Size = v.size();
    bool pos = false;
 
        for (int i = 1; i <= Size / 2; i++) {
            pos = false;
            for (int j = 0; j < i; j++) {
                if (v[Size - 1 - j] != v[Size - 1 -j- i]) pos = true;
            }
            if (pos == false) return pos;
            
        }
        return pos;
}
 
void func(vector<int> v) {
    if (v.size() > 1) {
        if (!good(v)) {//좋은수열이 아니면 return
            return;
        }
    }
    if (v.size() == N) {//좋은 수열이고 길이가 n이면 출력
        for (int i = 0; i < N; i++) {
            cout << v[i];
        }
        exit(0);//출력과동시에 exit.
    }
    vector <int> v1 = v;
    v1.push_back(1);
    func(v1);
    vector <int> v2 = v;
    v2.push_back(2);
    func(v2);
    vector <int> v3 = v;
    v3.push_back(3);
    func(v3);
}
 
 
 
 
int main() {
    cin >> N;
    vector<int> a;
    func(a);
}