초이로그

이전의 숨바꼭질 시리즈와는 다르게 시간에 따라 동생의 위치가 바뀐다. == 이전에 방문했던 좌표를 재방문할 수 있다. (최소시간을 위해) == BFS로만 돌리면 메모리 초과를 맛볼 수 있다. 역시 골드1의 문제... 약간의 아이디어가 필요했다. 헤이 구글 1. 재방문의 경우, 최소 2초가 걸린다. 2. 수빈이가 각 좌표에 도달하는 최초 시간을 구한다. 즉, 각 좌표에 도달하는 최소 시간을 구한다면, 해당 좌표는 언제나 2n초 안에 돌아올 수 있다. 2n초 안에 재방문 가능하다는 것은, 최초 시간이 홀수라면 언제나 홀수 시간에, 최초 시간이 짝수라면 언제나 짝수 시간에 방문 가능하다는 것이다. 따라서 짝수로 최초 도달하는 시간, 홀수로 최초 도달하는 시간을 구분해야한다. int[][] vis = new i..

이정도 난이도의 구현문제가 그렇듯 "오? bfs/dfs 써서 구현만 딱하면 될거 같은데?" 하고 덤비면 점점 꼬이는 문제.. 7달전의 나처럼.. 게임이 진행되는 것과 같이 차근차근 케이스를 나누고 적절한 알고리즘을 대입하면 쉽게 해결할 수 있다. 1. 궁수를 배치한다. -> M개의 자리중 3개를 선택하는 문제이므로 재귀를 사용하여 조합을 구현 private static void combination(int cnt, int st) { if (cnt == 3) { // 궁수 3명 자리 고르기 완료! 조합 완성! } else { for (int i = st; i < M; i++) { archers[cnt] = i; combination(cnt + 1, i + 1); } } } 2. 완성된 조합에서, 몇명의 적..