[백준] 2091번 동전 (gold 3

import java.io.*;
import java.util.*;

public class Main {
    static int[][] num;
    static int row; //행의 값
    static int index; //10자리수에서 앞쪽인지 뒤쪽인지.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.valueOf(st.nextToken());
        int a = Integer.valueOf(st.nextToken());
        int b = Integer.valueOf(st.nextToken());
        int c = Integer.valueOf(st.nextToken());
        int d = Integer.valueOf(st.nextToken());

        num = new int[3][x + 1];
        //작은 수부터 큰 수로 배낭이론 dp
        //a,b(0 c,d(1열로 묶어서 10자리수.(10억이하) 두개로 각각의 갯수를 저장.
        //2열은 두 코인들의 갯수합.
        //배낭이론은 2행, x열인데, 이때 ,a,b,c,d의 저장 인덱스와 위치가
        //다르므로 따로 지정해야됨. 배낭알고리즘을 메소드로 구현하고
        //a,b,c,d마다 행과 위치를 조절하여, 알맞은 위치로 저장.
        row = 0;
        index = 0;
        bag(1, a, x);
        row = 0;
        index = 1;
        bag(5, b, x);
        row = 1;
        index = 0;
        bag(10, c, x);
        row = 1;
        index = 1;
        bag(25, d, x);

        if (num[2][x] == 0) {
            bw.write("0 0 0 0");
        } else {
            bw.write(num[0][x] / 100000 + " " + num[0][x] % 100000 + " " + num[1][x] / 100000 + " " + num[1][x] % 100000);
        }
        bw.flush();
    }

    public static void bag(int coin, int count, int x) {
        for (int i = 1; i <=x; i++) {
            //0개이면 해당 작업 못함.
            if ((num[2][i] == 0 && coin == i) && count>0) {
                if (index == 0) {
                    num[row][i] = 1 * 100000;
                } else {
                    num[row][i] = 1;
                }
                num[2][i] = 1;
            }
            //쭉가면서, 담은 상태서 그 다음을 생각하는 방식으로 겹쳐서 봐야됨.
            //시초문제때문에.
            //해당 코인의 갯수가 count보다 적어야 해당 작업시행
            //다른행도 저장해줘야됨.... ㅠㅠ 
            //한 행 참조하면서 업데이트시 당연히 다른 행도 해야됨. ....
            if ((num[2][i] != 0 && coin + i <= x) && (num[2][i] + 1 > num[2][i + coin])) {
                if (index == 0 && num[row][i]/100000+1<=count) {
                    num[row][i + coin] = (num[row][i] / 100000 + 1) * 100000 + (num[row][i] % 100000);
                    //요부분..
                    if(row==0){
                        num[1][i+coin]=num[1][i];
                    }else{
                        num[0][i+coin]=num[0][i];
                    }
                } else if(index==1 && num[row][i]%100000+1<= count){
                    num[row][i + coin] = num[row][i] + 1;
                    //요부분..
                    if(row==0){
                        num[1][i+coin]=num[1][i];
                    }else{
                        num[0][i+coin]=num[0][i];
                    }
                }
                else{
                    continue;
                }
                num[2][i + coin] = num[2][i] + 1;
            }
        }


    }
}