PS
코딩 테스트 공부 [프로그래머스]
깊게 생각하고 최선을 다하자
2022. 9. 20. 16:22
1. 문제에 대한 이해
- 우리가 풀어야 할 문제는 무엇인가?
- 주어진 자료는 무엇인가?
- 조건은 무엇인가?
- 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
- 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라.
2. 계획
- 전에 비슷한 문제를 알고 있는가?
- 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
- 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
- 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
- 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
- 자료는 모두 사용했는가?
- 조건을 모두 사용했는가?
- 문제에 포함된 핵심적인 개념은 모두 고려했는가?
3. 실행
- 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.
[내 풀이]
public class Main {
public static int[][] dp = new int[200][200];
public static int maxAlp = Integer.MIN_VALUE;
public static int maxCop = Integer.MIN_VALUE;
public int solution(int alp, int cop, int[][] problems) {
int answer = 0;
int cnt = 1;
for(int i=alp+1; i<=maxAlp; i++){
dp[i][cop] = cnt++;
}
cnt = 1;
for(int i=cop+1; i<=maxCop; i++){
dp[alp][i] = cnt++;
}
for(int i=alp; i<=maxAlp; i++){
for(int j=cop; j<=maxCop; j++){
for(int k=0; k<problems.length; k++){
int requiredAlp = problems[k][0];
int requiredCop = problems[k][1];
int proAlp = problems[k][2];
int proCop = problems[k][3];
int cost = problems[k][4];
if(i == alp && j == cop){
dp[i][j] = 0;
}else if(i == alp){
System.out.println("i, j는? " + i + " " + j);
System.out.println("before:" + dp[i][j]);
System.out.println(dp[i-1][j]+1);
System.out.println(dp[i][j-1]+1);
System.out.println(dp[i-alp][j-cop]+cost);
if(i >= alp+proAlp && j>=cop + proCop && (i-proAlp) >= requiredAlp && (j-proCop) >= requiredCop){
dp[i][j] = Math.min(dp[i][j], dp[i-alp][j-cop]+cost);
}else{
dp[i][j] = dp[i][j-1] + 1;
}
}else if(j == cop){
System.out.println("i, j는? " + i + " " + j);
System.out.println("before:" + dp[i][j]);
System.out.println(dp[i-1][j]+1);
System.out.println(dp[i][j-1]+1);
System.out.println(dp[i-alp][j-cop]+cost);
if( (i >= alp+proAlp) && (j>=cop + proCop) && ((i-proAlp) >= requiredAlp) && ((j-proCop) >= requiredCop)){
dp[i][j] = Math.min(dp[i][j], dp[i-alp][j-cop]+cost);
}else{
dp[i][j] = dp[i-1][j] + 1;
}
}else{
System.out.println("i, j는? " + i + " " + j);
System.out.println("before:" + dp[i][j]);
System.out.println(dp[i-1][j]+1);
System.out.println(dp[i][j-1]+1);
System.out.println(dp[i-alp][j-cop]+cost);
if( (i >= alp+proAlp) && (j>=cop + proCop) && ((i-proAlp) >= requiredAlp) && ((j-proCop) >= requiredCop)){
dp[i][j] = Math.min(dp[i-1][j]+1, dp[i][j-1]+1);
dp[i][j] = Math.min(dp[i][j], dp[i-alp][j-cop]+cost);
}else{
dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1]+ 1);
}
System.out.println("after:" + dp[i][j]);
}
}
}
}
answer = dp[maxAlp][maxCop];
for(int i=alp; i<=maxAlp; i++){
for(int j=cop; j<=maxCop; j++){
System.out.print("(" + i + ")" + " (" + j + ") " + dp[i][j]+ " ");
}
System.out.println();
}
return answer;
}
public static void main(String args[]) {
Main T = new Main();
int[][] problems = {{10, 15, 2, 1, 2}, {20, 20, 3, 3, 4}};
int len = problems.length;
for(int i=0; i<len; i++){
maxAlp = Math.max(maxAlp, problems[i][0]);
maxCop = Math.max(maxCop, problems[i][1]);
}
int result = T.solution(10, 10, problems);
System.out.println(result);
}
}
[참고 풀이]
class Solution {
public int solution(int alp, int cop, int[][] problems) {
int answer = 0;
int maxAlp = Integer.MIN_VALUE;
int maxCop = Integer.MIN_VALUE;
for(int i=0; i<problems.length; i++){
maxAlp = Math.max(maxAlp, problems[i][0]);
maxCop = Math.max(maxCop, problems[i][1]);
}
if(alp >= maxAlp){
alp = maxAlp;
}
if(cop >= maxCop){
cop = maxCop;
}
int[][] dp = new int[maxAlp+10][maxCop+10];
for(int i=alp; i<=maxAlp; i++){
for(int j=cop; j<=maxCop; j++){
dp[i][j] = Integer.MAX_VALUE;
}
}
dp[alp][cop] = 0;
for(int i=alp; i<=maxAlp; i++){
for(int j=cop; j<=maxCop; j++){
dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]+1);
dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j]+1);
for(int k=0; k<problems.length; k++){
int requiredAlp = problems[k][0];
int requiredCop = problems[k][1];
int addedAlp = problems[k][2];
int addedCop = problems[k][3];
int cost = problems[k][4];
if(i>=requiredAlp && j>= requiredCop){
if(i+addedAlp > maxAlp && j+addedCop > maxCop){
dp[maxAlp][maxCop] = Math.min(dp[maxAlp][maxCop], dp[i][j]+cost);
}else if(i+addedAlp > maxAlp){
dp[maxAlp][j+addedCop] = Math.min(dp[maxAlp][j+addedCop], dp[i][j]+cost);
}else if(j+addedCop > maxCop){
dp[i+addedAlp][maxCop] = Math.min(dp[i+addedAlp][maxCop], dp[i][j]+cost);
}else{
dp[i+addedAlp][j+addedCop] = Math.min(dp[i+addedAlp][j+addedCop], dp[i][j]+cost);
}
}
}
}
}
if(alp >= maxAlp && cop >= maxCop){
answer = 0;
}else{
answer = dp[maxAlp][maxCop];
}
return answer;
}
}4. 반성
- 문제를 다른 방식으로 해결할 수 있는가?
- 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
- 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?
- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
-> DP로 접근한다는 아이디어를 갖는다
-> 예외 케이스를 잘 고려한다
-> alp와 cop가 둘 다 maxAlp, maxCop보다 크면 0이다
-> alp가 maxAlp보다 크면 alp에 maxAlp를 대입한다
-> 이것을 하는 이유는 둘 중 하나만 클 수도 있기 때문이다.
-> 그렇다면 나머지 하나에 대해서 해야 한다
-> 하지만 우리는 큰 값에 대해서는 관심이 없다
-> 그런데 이 큰 값이 들어갈 수도 있다는 점을 고려해야 한다
-> 큰 값이 들어갈 수도 있다는 점을 고려해야 한다
-> 어디에 들어가는가?