[S/W 문제해결 응용] 2일차 - 최대 상금

 

문체 출처 https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

 

BFS도 우선순위 큐도 전부 안됐던 문제 최대가 7개 정답까지 였다. 시간 초과를 해결 하기 위한 방법으로 DFS를 써야 했는데 결국 swap이 일어나야 하는데 아이디어로 전부 어떤 규칙에 대해서 한번에 커지는 방향만으로 가는 것은 불가능 하고, 결국 DFS 혹은 BFS로 모든 케이스를 다 찾아봐야 하는 문제였다.

우선 i,j 인덱스를 스왑을 하고 그 상태로 재귀한다. 그리고 다시 원상복구 한다. 재귀 상태는 i,j가 스왑된 상태로 끝까지 진행되고 인덱스 i,j 가 스왑된 후에 발생되는 모든 케이스에 대해 전부 탐색한다. 그때 만약 num만큼 스왑을 완료 했을 때의 string의 값과 maxa의 값을 비교해서 더 큰값을 maxa 저장해 놓으면 다음 탐색시 계속 업데이트가 된다.

그래서 num까지 이른 모든 케이스가 maxa에 업데이트를 시도하고 전부 return되므로 마지막에 저장되있는 maxa가 

해당 스트링의 정해진 반복 횟수에 대한 최대 값이다. 

 

#include <iostream>
#include <algorithm>
#include  <string>