[백준] 2661 - 좋은 수열 (C++)

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

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있는 수열을 '나쁜 수열'이라고 부른다. 그렇지 않으면 좋은 수열이다. 길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 구하는 문제다.

 

나쁜 수열의 예시는 아래와 같다.

• 33, 32121323, 123123213

 

좋은 수열의 예시는 아래와 같다.

• 2, 32, 32123, 1232123

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 80

 

N자리의 정수 중 조건(좋은 수열)에 맞는 가장 작은 수만 출력해야 하기 때문에 한 번 출력하고 나면 프로그램을 종료시켜야 한다. 추가로, 마지막으로 붙인 숫자와 붙이려는 숫자가 같은지 확인하면 시간을 좀 더 줄일 수 있다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N 입력받기
2. 정수 뒤에 1, 2, 3을 붙여가며 백트래킹 함수 진행
   1. 정수의 마지막 숫자와 붙이려는 숫자가 같은 경우 continue
   2. 정수 뒤에 숫자를 붙인 후 정수가 유망하면 백트래킹 함수 진행
      1. substr() 함수로 겹치는 인접한 부분 수열이 있는지 검사 → 있다면 유망하지 않음
   3. 정수 뒤에 붙인 숫자 제거
3. 정수의 길이가 N이면 정수를 출력하고 프로그램을 종료

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

int n;
string str;

bool proper(string s) {
    int ss = s.size();
    for (int i=1; i<=ss/2; i++) {
        if (s.substr(ss-2*i,i)==s.substr(ss-i,i)) return false;
    }
    return true;
}

void dfs(int dep) {
    if (dep==n) {
        cout << str;
        exit(0);
    }
    for (int i=1; i<=3; i++) {
        int ss = str.size();
        if (str[ss-1]==i) continue;
        str.push_back('0' + i);
        if (proper(str)) dfs(dep+1);
        str.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;

    dfs(0);
}