백준 2661 좋은수열 C++

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

2661번: 좋은수열

1,2,3으로만 이루어진 수열 중 좋은 수열의 최소값을 찾는 문제입니다.

 

좋은 수열은 임의의 인접한 두 부분수열이 동일한 것이 없는 것으로 다음은 나쁜 수열입니다.

 

ex. 33 / 123123 / 12323 

 

1,2,3 3개의 수만 이용하여 구하는 것이므로 빈 string에 1,2,3을 하나씩 넣어보며 나쁜 수열이 나오는 경우 진행을 중단합니다. 1,2,3 순으로 dfs를 진행하기 때문에 가장 처음으로 좋은 수열이 나오는 경우가 최솟값입니다.

 

좋은 수열임을 판단하는 것은 나쁜 수열이 될 수 있는 경우를 간격을 늘려가며 계속 체크하며 확인하면 됩니다. 

123 이라는 수열에 1이 새로 들어오면 1231 => 12 / 31 확인 => 좋은 수열

12312 라는 수열에 3이 새로 들어오면 12 31 / 23 확인, 123 / 123 확인 => 나쁜 수열 

 

코드는 다음과 같습니다.