BACKTRACING
-
좋은수열백준알고리즘 2019. 9. 5. 01:44
백트래킹 문제로, 어려운 문제라기보단 귀찮은 문제가아닐까 싶었고, 확신이 쉽게들지않을문제. 첫번째, 일단 재귀를통해 수열을 만드는것은 string을 통해 쉽게 가능함 두번째, 바로앞에 중복되는 값을 수열로만드는건 굉장히 쉬움 세번째, 세번째부터 문제인데, 앞서 사용되있던 문자들과 중복체크하는것 이 굉장히 귀찮다. 하나하나 다해보기엔 시간복잡도가 터져버릴것같은문제, 전략을 세워보면, 딱 반크기만큼만 잘라서 보면된다 전체적으로 다검사해봐야하는것은 맞지만, 이어붙여나가는과정에서 이미 이어붙였던 것까지 한번에 검사할필요는 없다는얘기다. 문제를 풀어서 코드로 작성해보면다음과같다. #include #include #include #include using namespace std; vector a[80]; char..