이것이 취업을 위한 코딩테스트다. Chapter08

import java.util.*;
public class main {
    public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.Chap08Example01TopDown(26));
    System.out.println(s.Chap08Example01BottomUp(26));
    System.out.println(s.Chap08Example02BottomUp(4, new int[]{1,3,1,5}));
    System.out.println(s.Chap08Example02TopDown(4, new int[]{1,3,1,5}));
    System.out.println(s.Chap08Example03BottomUp(3));
    System.out.println(s.Chap08Example03TopDown(3));
    System.out.println(s.Chap08Example04TopDown(2,15,new int[] {2,3}));
    System.out.println(s.Chap08Example04TopDown(3,4,new int[] {3,5,7}));
    System.out.println(s.Chap08Example04BottomUp_Guide(2,15,new int[] {2,3}));
    System.out.println(s.Chap08Example04BottomUp_Guide(3,4,new int[] {3,5,7}));
    }
}
class Solution {

    public int Chap08Example01TopDown(int n) {
        int[] memory = new int[n+1];

        return Example01TopDown(n, memory);
    }
    public int Chap08Example01BottomUp(int n) {
        int[] memory = new int[n+1];
        for(int i = 2; i<=n;++i) {
            int d5 = 300001;
            if(i % 5 == 0) {
                d5 = memory[i/5]+1;
            }
            int d3 = 300001;
            if(i % 3 == 0) {
                d3 = memory[i/3]+1;
            }
            int d2 = 300001;
            if(i % 2 == 0) {
                d2 = memory[i/2]+1;
            }
            int m1 = memory[i-1]+1;
            int min = (d5 < d3) ? d5 : d3;
            min = (min < d2) ? min : d2;
            min = (min < m1) ? min : m1;
            memory[i] = min;
        }
        return memory[n];
    }
    public int Example01TopDown(int n, int[] memory) {
        if(n == 1) {
            return 0;
        }
        if(memory[n] != 0) {
            return memory[n];
        }
        else {
            int d5 = 300001;
            if( n % 5 == 0) {
                d5 = Example01TopDown(n /5 , memory)+1;
            }
            int d3 = 300001;
            if(n % 3 == 0) {
                d3 = Example01TopDown(n/3, memory)+1;
            }
            int d2 = 300001;
            if(n % 2 == 0) {
                d2 = Example01TopDown(n/2, memory)+1;
            }
            int m1 = Example01TopDown(n-1, memory)+1;

            int min = (d5 < d3) ? d5 : d3;
            min = (min < d2) ? min : d2;
            min = (min < m1) ? min : m1;
            memory[n] = min;
            return memory[n];
        }
    }
    public int Chap08Example02BottomUp(int n, int[] foods) {
        int[] maxFoods = new int[n];

        maxFoods[0] = foods[0];
        maxFoods[1] = (foods[0] > foods[1]) ? foods[0] : foods[1];
        for(int i = 2; i<n;++i) {
            maxFoods[i] = (maxFoods[i-1] > maxFoods[i-2]+foods[i]) ? maxFoods[i-1] : maxFoods[i-2]+foods[i];
        }
        return maxFoods[n-1];
    }
    public int Chap08Example02TopDown(int n, int[] foods) {
        int[] memory = new int[n];
        memory[0] = foods[0];
        memory[1] = (foods[1] > foods[0]) ? foods[1] : foods[0];
        Example02TopDown(n-1, memory, foods);
        return memory[n-1];
    }
    public int Example02TopDown(int n, int[] memory, int[] foods) {
        if(memory[n] != 0) {
            return memory[n];
        }
        int n1 = Example02TopDown(n-1, memory, foods);
        int n2 = Example02TopDown(n-2, memory, foods)+foods[n];
        memory[n] = (n1 > n2) ? n1 : n2;
        return memory[n];
    }
    public int Chap08Example03BottomUp(int n) {
        int[] memory = new int[n+1];
        memory[1] = 1;
        if(n == 1)
            return memory[1];
        memory[2] = 3;
        if(n == 2)
            return memory[2];
        for(int i = 3; i<=n;++i) {
            memory[i] = memory[i-1]+ memory[i-2]*2;
        }
        return memory[n]%796796;
    }
    public int Chap08Example03TopDown(int n) {
        int[] memory = new int[n+1];
        if(n>=1) {
            memory[1] = 1;
        }
        if(n>=2) {
            memory[2] = 3;
        }
        Example03TopDown(n, memory);
        return memory[n];
    }
    public int Example03TopDown(int n, int[] memory) {
        if(memory[n] != 0)
            return memory[n];
        memory[n] = Example03TopDown(n-2, memory) *2 + Example03TopDown(n-1,memory);
        return memory[n];
    }
    public int Chap08Example04TopDown(int n, int m, int[] coins) {
        int[] memory = new int[m+1];
        for(int c : coins) {
            if(c <= m)
                memory[c] = 1;
        }
        Example04TopDown(m,coins,memory);
        if(memory[m] == 10001) {
            return -1;
        }
        return memory[m];
    }
    public int Example04TopDown(int m, int[] coins, int[] memory) {
        if(m == 0)
            return 0;
        if(memory[m] != 0) {
            return memory[m];
        }
        int min = 10001;
        int tmp = 0;
        for(int c : coins) {
            if(m-c >= 0) {
                tmp = Example04TopDown(m-c, coins, memory)+1;
                min = (min < tmp) ? min : tmp;
            }
        }
        memory[m] = min;
        return memory[m];
    }
    public int Chap08Example04BottomUp_Guide(int n, int m, int[] coins) {
        int[] memory = new int[10001];
        Arrays.fill(memory,10001);//기억해두자. for문 반복 돌리지 말고..
        memory[0] = 0;
        for(int i = 0; i < n;++i) {
            for(int j = coins[i]; j<=m;++j) {
                if(memory[j-coins[i]] != 10001) {
                    memory[j] = (memory[j] < memory[j-coins[i]] +1) ?  memory[j] : memory[j-coins[i]] + 1;
                }
            }
        }
        if(memory[m] == 10001)
            return -1;
        return memory[m];
    }
}

---

다른 챕터와 DP는 언제나 사람 머리 아프게 하는 파트다. Top-Down, Bottom-Up이 어려운 것은 아니지만 이 문제가 DP로 풀어야 하는지를 빠르게 인지를 하는 것이 중요하다. 그리고 DP로 풀었다 하더라도 정확한 공식을 찾아야 한다.

Example03 바닥 공사 문제에서 경우의 수가 어떻게 되는지 문제만 보고서는 이해가 안가서 그림을 그려보았는데도 아리까리했다.

평소에는 항상 재귀로 문제를 푸는게 습관처럼 되어있어서 Bottom-Up을 사용하는 연습을 들이고자 Top-Down, Bottom-Up을 같이 써봤다.

Example04는 Bottom-Up으로 될거라고 생각도 안했는데..

징글맞게 어렵다 진짜..