[백준,c++] 16719번 - ZOAC

문제

16719번: ZOAC

 

코드

#include <iostream>
using namespace std;

string s;
bool visited[101];
void backtracking(int start, int end){
    if(start == end) return;
    char c = '~';
    int idx = 0;
    for(int i=start; i<end; i++){
        if(s[i] < c){
            c = s[i];
            idx = i;
        }
    }
    visited[idx] = 1;
    for(int i=0; i<s.length(); i++){
        if(visited[i]) cout<<s[i];
    }
    cout<<'\n';
    backtracking(idx + 1, end);
    backtracking(start, idx);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>s;
    backtracking(0, s.length());
}

 

풀이

문제 이해는 했는데, 접근을 어떻게 해야 할지 도저히 떠오르지 않아서 검색을 하다가 아래 블로그의 접근 방법을 참고했습니다.

[BOJ] 백준 16719 ZOAC

STARTLINK 문자열을 예로 들면 다음과 같습니다.

1) 우선 전체 구간 중 가장 작은 문자는 A이다.

A에 체크 후 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O

 

2) A를 기준으로 오른쪽구간 [3, 8]에서 같은 과정을 거친다.

가장 작은 문자 I에 체크 후 체킹 된 문자들을 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O				O

 

3) I 기준 오른쪽구간 [7, 8]에서 가장 작은 문자인 K에 체크 후 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O				O		O

 

4) K의 오른쪽 구간이 없으므로 왼쪽 구간 [7, 7]의 가장 작은 문자인 N에 체크 후 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O				O	O	O

 

5) I 의 오른쪽 구간을 다 봤으니 왼쪽 구간 [3, 5]에서 가장 작은 문자인 L에 체크 후 출력한다.

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력			O			O	O	O	O

 

6) L의 왼쪽구간 [3, 4]에서...

문자	S	T	A	R	T	L	I	N	K
인덱스	0	1	2	3	4	5	6	7	8
출력	O	O	O	O	O	O	O	O	O