2661번 좋은 수열(DFS, str.substr(), equal(), DFS한번 출력) - ☆

#문제링크 : https://www.acmicpc.net/problem/2661

출처 : https://m.blog.naver.com/PostView.nhn?blogId=and_lamyland&logNo=221372279407&proxyReferer=https:%2F%2Fwww.google.com%2F

전략 : 이 문제의 특징은 숫자가 12322이면 먼저 1. ( 2 / 2 ) 비교, 2. ( 2 3 / 2 2 ) 비교, 총 2번 비교, 숫자가 123이면 1. ( 2 3 ) 비교, 총 1번 비교. 숫자가 23121132이면 1. ( 3 / 2 ), 2. ( 1 1 / 3 2 ), 3. ( 1 2 1 / 1 3 2 ), 4. ( 2 3 1 2 / 1 1 3 2 ), 총 4번 비교한다. 이와같은 특징을 보면 전체 숫자의 자릿수가 N이라면 총 N/2번 비교를 진행해보고 같으면 뺀 후에 다른 숫자를 넣고 다르면 그대로 다음 숫자를 또 넣으면 된다. 비교 방식이 숫자로 비교하는 것보다 문자열로 비교하는 것이 더 수월하다. 이유는 string.substr() 함수, string.compare() 함수와 equal()함수를 사용하면 쉽게 비교가 가능하기 때문.

※주의사항

1. DFS이지만 전체 경우의 수를 전부 출력하는게 아니고 가장 작은, 즉 처음 조건을 만족하는 숫자 하나만 출력.

2. substr함수와 compare함수의 사용법 숙지.

3. 인자로 문자를 더할때, dfs(s + (char)(i + '0'))와 같이 한다.

1. Code

출처 : https://www.crocus.co.kr/657

※주의사항

1. equal함수의 사용법 숙지.

2. 마지막 for문이 끝났을 때, return 값이 존재 하지 않을 수 있기에 재귀의 흐름을 잘 따라가서 반례 놓치지 않기.

2. Code