[SWEA] 1244 최대상금
쉬운줄알았는데 좀 고민하게 해준 문제다 먼저 비슷만 문제는 백준의 숨바꼭질 5(https://sejinik.tistory.com/194)다 이 문제는 모든 경우를 DFS로 다 해보면 답이 나오지만 그냥 하면 시간초과 난다 그럼 시간을 줄이기 위해서 어떻게 해야할까? 한번 생각해보자 내가 홀수일때 방문한곳은 다음 홀수에도 방문할 수 있다 반대로 짝수도 마찬가지다 예를들어 123-213-123 이런식으로 2차이나면 원래자리로 다시 돌아올 수 있다 그럼 우리는 방문할 수 있는 숫자 중에서 홀,짝으로 나눠서 방문했는지 체크를 해보면 된다! 내가 만약 다음 방문할 곳에 홀수번만에 갈 때 이전에 홀수번에서 방문했다면 방문하지않는다! 아니라면 방문하면된다!! 그럼 시간안에 dfs를 통해 답을 찾아갈 수 있다! 소스코..
알고리즘/Java
2020. 2. 17. 17:39