룰루랄라 알고리즘

무작위 좌표 3개를 어떻게 구성할지 고민하다가 중복순열 prodct 라이브러리를 활용해 풀었다. 조건 중에 꽃이 벽을 넘어서면 안된다고 제시 했기 때문에 좌표를 1~N-1로 제한 했다. for문과 함수호출을 많이 하는 코드라서 시간 초과가 나오지 않을까 걱정했는데 느리긴 하지만 시간내에 통과했다. 21~28줄의 예외처리 코드를 작성하지 않고 제출해 틀렸다가 수정했다. 비용이 모두 0이면 0을 출력해야 하는데 result에 초기 설정된 최댓값이 출력되어 수정했다.

DFS를 활용한 백트래킹으로 문제를 풀었다. 사실 DFS를 안쓰고 백트래킹 하는 법을 잘 모르겠다. 아무튼 코드가 복잡하다 다른 분이 푼 코드에 비해 현저히 길다. 내가 푼 방식으로 봤을 때 키포인트는 1. 33,34줄에서 방문처리와 pop() DFS를 활용한 백트래킹에서 가장 중요한 부분인것 같다. 2. 56줄 부터 나오는 join int형은 길이를 셀 수 없기때문에 str형태로 바꿔서 max_num의 길이를 측정하고, 리스트에 str로 append해서 str(0) 과 join했다. join은 str형태 밖에 쓸 수 없다. 아래는 다른 사람이 푼 코드를 보고 따라한 방식이다. max_num, min_num을 처음부터 str형태로 저장했다. 위 풀이는 아무리봐도 이해가 안된다. 절대 내가 생각해 낼 수 ..

백준 14888번 내 기준 dfs를 활용한 백트래킹 정석 문제 1. modify 리스트에 연산자의 개수를 저장 2. dfs 함수로 깊이 depth, 총 점수 total, 연산자의 개수를 변수로 넘김 3. 깊이가 N이 될 때 마다 total의 최댓값, 최솟값을 저장하고 함수를 빠져나오면 깊이가 N-1인 다른 dfs 함수가 실행되어 또 다시 total의 최대,최소 판별 4. 이렇게 모든 경우의 수를 백트래킹으로 판별가능

원래는 브루트 포스로 하나하나 대입해서 풀었는데 코드도 더럽고 내 취향이 아니라 다르게 풀어봤음 DFS를 이용하여 값을 더해가는 풀이 idx = 1 일 때(즉, 두개의 블럭을 선택했을 때) 새로운 블럭에서 다음 블럭을 탐색하는 것이 아니라 다시 기존블럭에서 탐색하게 만들면 ㅗ,ㅏ,ㅓ,ㅜ 모양을 만들 수 있다. 가지치기 하는 코드 2차원배열에서 최대값을 찾아서 max(map(max, graph)) 선택할 수 있는 남은 블럭의 갯수만큼 (3 - idx) 곱해주고 현재 누적합 total 에 더해서 max_result 와 비교해주는 방식 가지치기 안하니까 시간초과 나옴 ***방문처리 주의하자***