뮤탈리스크 [BOJ 12869]
1. 문제에 대한 이해
- 우리가 풀어야 할 문제는 무엇인가?
- 주어진 자료는 무엇인가?
- 조건은 무엇인가?
- 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
- 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라.
- 문제가 무엇인가?
-> 어떻게 탐색 횟수를 최소화할 것인가?
-> 만약 allDead가 아닌 상황에서 어떻게 체크할 것인가?
-> 죽은 것을 어떻게 체크할 것인가?
-> 죽었다는 것이 무엇인가?
-> 죽으면?
-> 만약에 9 3 1 을 사용하는데, 3과 1이 죽었다고 해보자
-> 무슨 일이 발생하는가?
-> 만약에 9,3,1을 갖고 있었다고 해보자
-> 그렇다면 무엇을 없애야 하는가?
-> 이렇게 넣는 것이 맞는가?
-> damage가 3개일 때 어떤 일이 발생하는가?
-> 핵심이 무엇인가?
-> 9, 3이 남는다는 것이 핵심이다
-> 이 의미가 무엇인가?
-> 문제가 무엇인가?
-> 어떻게 정의내리는가?
-> 어떻게 검사를 하는가?
-> 어떻게 복구를 하는가?
-> 복구를 한다는 것이 무엇인가?
->
- 좀 더 깊게 생각해보자
-> 문제가 무엇인가?
-> 왜 문제가 발생하는가?
-> 9, 3, 1이고, 9,1,3, 3,9,1 3,1,9 1,9,3 1,3, 9
-> 이 여섯가지 중에 아무거나 하면 된다.
-> 이것을 어떻게 적용하는가?
-> 적용한다는 것이 무엇인가?
->
-> 9, 3이고
-> 9이다
-> 이것을 잘 적용해야 한다
-> 적용해서 제거해줘야 한다
-> 그리고 scv에 삭제를 반영해야 한다
-> 어떻게 삭제를 반영하는가?
->
9 3 1
9 1 3
3 9 1
3 1 9
1 9 3
1 3 9
- 문제가 무엇인가?
-> 계속 시간 초과가 뜬다
-> 이유가 무엇인가?
-> 3차원 배열을 선언해야 하는가?
-> dp에 기록한다는 것이 무엇인가?
-> 왜 기록하는가?
-> 여섯가지 공격패턴을 한다는 것이 무엇인가?
-> 왜 여섯가지 공격패턴을 하는가?
-> 이것을 어떻게 하는가?
-> 왜 이렇게 코드를 짜는가?
->
2. 계획
- 전에 비슷한 문제를 알고 있는가?
- 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
- 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
- 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
- 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
- 자료는 모두 사용했는가?
- 조건을 모두 사용했는가?
- 문제에 포함된 핵심적인 개념은 모두 고려했는가?
3. 실행
- 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.
[참고 풀이]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int[] scv;
public static int[][] delta = {{-9, -3, -1}, {-9, -1, -3}, {-3, -9, -1}, {-3, -1, -9}, {-1, -9, -3}, {-1, -3, -9}};
public static int[][][] dp;
public static int N;
public static int min;
public static void DFS(int[]scv, int cnt){
int s1 = scv[0];
int s2 = scv[1];
int s3 = scv[2];
if(min <= cnt){
return;
}
if(dp[s1][s2][s3] != 0 && dp[s1][s2][s3] <= cnt) return;
dp[s1][s2][s3] = cnt;
if(s1 == 0 && s2 == 0 && s3 == 0){
min = Math.min(min, cnt);
return;
}
for(int i=0; i<6; i++){
DFS(new int[]{Math.max(s1+delta[i][0], 0), Math.max(s2+delta[i][1], 0), Math.max(s3+delta[i][2], 0)}, cnt+1);
}
}
public static void main(String[] args) throws IOException{
Main T = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] scv = new int[3];
for(int i=0;i<N;i++) {
scv[i] = Integer.parseInt(st.nextToken());
}
dp = new int[61][61][61];
min = Integer.MAX_VALUE;
DFS(scv,0);
System.out.println(min);
}
}4. 반성
- 문제를 다른 방식으로 해결할 수 있는가?
- 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
- 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?