2661: 좋은수열

문제 링크

2661: 좋은수열

구현 방식

• backtracking 유형의 문제이다

  • 뒤에 숫자를 "하나씩" 붙여가면서 좋은수열을 만족하는 지 check_curr함수를 통해 확인해주면서 backtracking을 진행해주면 된다

• check_curr 함수는 "하나의 숫자"를 붙였을 때 좋은 수열을 만족하는 지를 확인하는 함수

  • 따라서 뒤에서부터 len(seq)//2만큼만 확인해주면 된다
  • (python에서는 index를 이용한 문자열 slicing, c++에서는 seq.substr(시작인덱스, 문자열길이)를 이용했다. 또한, c++에서 int를 string type으로 casting할 때는 to_string()을 이용함)

코드

#include <iostream>
#include <string>
using namespace std;

int N;
string seq;
bool done = false;

bool check_curr(string seq){
    int n = seq.size();
    for (int i=1; i<=int(n/2); i++){
        if (seq.substr(n-i, i) == seq.substr(n-2*i, i)){ //substr(시작인덱스, 문자열길이)
            return false;
        }
    }
    return true;
}

void backtracking(string seq){
    if (done) return;
    if (seq.size() == N){
        cout << seq;
        done = true;
    }
    else{
        for (int i=1; i<3+1; i++){
            if (check_curr(seq+to_string(i))){ //int -> string to_string 사용
                backtracking(seq+to_string(i)); 
            }
        }
    }
}

int main() {
    cin >> N;
    backtracking("1");

    return 0;
}

import sys

def check_curr(seq): #"하나의 숫자"를 붙였을 때 좋은 수열을 만족하는 지 확인하는 함수
    n = len(seq)
    for i in range(1, n//2+1):
        if seq[-i:] == seq[-2*i:-i]: return False
    return True

def backtracking(seq):
    if len(seq) == N:
        print(seq); exit() #길이가 N인 좋은 수열을 찾은 경우, 바로 프로세스 종료
    else:
        for i in range(1, 3+1):
            if check_curr(seq+str(i)): #하나의 숫자 붙였을 때 좋은 수열을 만족하는 지 확인
                backtracking(seq+str(i))
    
N = int(sys.stdin.readline()[:-1])
backtracking('1')