백준 2661 좋은 수열

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

풀이

좋은 수열 중 가장 작은 값을 구하는 문제로 ==백트래킹==으로 풀 수 있다.

사실 모든 경우를 계산하면 $2^{80}$ 의 경우의 수가 나오기 때문에 안될 것 같다는 생각을 했었지만 중간에 좋은 수열이 아닌 경우인 애들이 빠지면서 시간 내에 풀리게 된다.

또한, 좋은 수열임을 판단할 때도 막 돌려도 시간 내에 풀린다.

코드

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> s;

bool isBad() {
    int size=s.size()/2;
    for(int i=2; i<=size; ++i) {
        bool flag=true;
        for(int j=0; j<i; ++j) {
            if(s[s.size()-i+j]!=s[s.size()-2*i+j]) {
                flag = false;
                break;
            }
        }
        if(flag)
            return true;
    }
    return false;
}

void solve(int n) {
    if(isBad())
        return;
    if(n==N) {
        for(auto &c:s) {
            cout<<c;
        }
        exit(0);
    }
    for(int i=1; i<=3; ++i) {
        if(s.back()!=i) {
            s.emplace_back(i);
            solve(n+1);
            s.pop_back();
        }
    }
}
int main() {
    cin>>N;
    s.emplace_back(1);
    solve(1);
    return 0;

}

생각보다 지저분하게 풀어서 마음에 안들었는데 isBad 함수를 간단히 내장된 eqaul 함수로 표현할 수 있음을 발견했다.

std::eqaul

😄

algorithm 헤더의 함수로 Test whether the elements int two ranges are eqaul

template <class InputIterator1, class InputIterator2>
bool equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
  while (first1!=last1) {
    if (!(*first1 == *first2))   // or: if (!pred(*first1,*first2)), for version 2
      return false;
    ++first1; ++first2;
  }
  return true;
}

내부 함수를 보니까 확실히 iterator를 잘 쓰는게 코드가 깔끔한듯!!

Written by@[jungin]

안녕하세요

GitHub