CodeJam 2013 Round 1A. Problem B. Manage your Energy 질문입니다.

  • teuskim3
    teuskim3

    알고스팟에 등록되어 있는 문제가 아닌데 질문을 해도 되는지 모르겠네요..혹시나 친절한 분의 도움을 받을 수 있을까 해서 민망한 소스코드 올리고 질문드립니다..^^;;

    이번 코드잼 1라운드 문제였습니다.
    에너지 최대치가 정해져 있고, activity들을 수행할때 소비되는 에너지와 수행후 보상되는 에너지들이 주어질 때, 각 (activity들의 가치) * (사용하는 에너지) 의 총합의 최대값을 구하는 문제입니다.

    저는 이것을 분할정복법으로 풀어보려고 했는데, small input에 대해서는 올바른 output이 나오는데, large input에 대해서는 몇몇 케이스가 정답보다 작은 값이 나옵니다.
    small input에서 오답이 나와야 뭔가 계산이라도 해보면서 오류를 찾아볼텐데, large input에서 오답이 나오니까 볼 엄두도 안나네요..
    종만님의 solution을 보고 훨씬 쉬운 해결방법에 대해서도 배웠고 이해도 했으나, 제가 풀던 방법에서도 문제가 무엇이었는지를 알아야 동일한 실수를 하지 않을것 같아서 질문 드립니다.
    이 알고리즘의 오류는 뭘까요?

    import java.util.Scanner;
    
    /**
     * CodeJam 2013 Round 1A
     * Problem B. Manage your Energy
     */
    public class B_qna {
    
        private int E,R,N;
        private int[] v;
    
        private void goodluck() throws Exception {
            // ready variables
            int numberOfCases;
    
            // get file
            Scanner sc = new Scanner(System.in);
            numberOfCases = sc.nextInt();
    
            // make output
            for(int casenum=0; casenum<numberOfCases; casenum++){
    
                E = sc.nextInt();
                R = sc.nextInt();
                N = sc.nextInt();
                v = new int[N];
                for(int i=0; i<N; i++) v[i] = sc.nextInt();
    
                String result = ""+solve(0, N-1, E, Math.min(R, E));
    
                System.out.println("Case #"+(casenum+1)+": "+result);
            }
        }
    
        /**
         * 분할정복방식을 사용하여 각 (energe)*(activity value) 총합의 최대값을 구한다.
         * 주어진 구간에서 최대값을 구하여 Vprev, Vmax, Vnext 로 구간을 분할하여 Vmax에 최선을 다한다.
         * Vmax에 최대한 E에 가까운 에너지를 사용할 수 있도록 Vprev에서는 가능한 최대의 에너지를 남겨준다.
         * 
         * @param sidx  v[]에 대한 start index
         * @param eidx  v[]에 대한 end index
         * @param se    start energy 구간 시작시 사용가능 에너지 
         * @param ee    end energy 구간이 끝날때 남아있어야 하는 에너지
         * @return  (energe)*(activity value) 총합의 최대값
         */
        private long solve(int sidx, int eidx, int se, int ee){
            if(sidx == eidx){
                int ue = se - ee + R;
                if(ue < 0) ue = 0;
                if(ue > E) ue = E;
                return ue * (long)v[sidx];
            }
    
            int vmaxIdx = 0;
            int vmax = Integer.MIN_VALUE;
            for(int i=sidx; i<=eidx; i++) if(v[i] > vmax){
                vmax = v[i];
                vmaxIdx = i;
            }
    
            long result = 0;
            int maxRecover,needRecover;
    
            // Vprev 에 대해 계산
            int nexte = se;
            if(vmaxIdx-1 >= sidx){
                maxRecover = R * (vmaxIdx-sidx);
                if(maxRecover < 0) maxRecover = 0;
                if(maxRecover > E) maxRecover = E;
                needRecover = E - se;
                if(needRecover < 0) needRecover = 0;
                if(needRecover > E) needRecover = E;
                if(maxRecover >= needRecover) nexte = E;
                else nexte = E-(needRecover-maxRecover);
                result += solve(sidx, vmaxIdx-1, se, nexte);
            }
    
            // Vmax 에 대해 계산
            maxRecover = 0;
            if(vmaxIdx+1 <= eidx){
                maxRecover = R * (eidx-vmaxIdx);
                if(maxRecover < 0) maxRecover = 0;
            }
            int ue = nexte + R + maxRecover - ee;
            if(ue < 0) ue = 0;
            if(ue > nexte) ue = nexte;
            result += ue * (long)v[vmaxIdx];
    
            // Vnext 에 대해 계산
            if(vmaxIdx+1 <= eidx){
                result += solve(vmaxIdx+1, eidx, Math.min(nexte-ue+R, E), ee);
            }
    
            return result;
        }
    
        public static void main(String[] args){
            try{
    
                new B_qna().goodluck();
    
            }catch(Exception e){
                e.printStackTrace();
            }
        }
    
    }
    

    11년 전
5개의 댓글이 있습니다.
  • JongMan
    JongMan

    작은 입력을 십만개쯤 만들어서 돌려보시면 틀리는걸 찾을 수 있지 않을까요? B번 이지 맞고 하드 푸신 분들 중 오버플로 나신 분도 많던데 그것도 한번 찾아보시고요. 저는 E < R 인 입력 처리 잘못할 뻔했는데 그것도 있나 한번 확인해 보세요.


    11년 전 link
  • xesmaster
    xesmaster

    종만이형 디피로 하신거같은데 어케 푸신건가효? ㅜㅜ 전 그리디하게 pq 이용해서 풀어봣는데 디피는 꿈에도 생각 못햇네요


    11년 전 link
  • iddaga
    iddaga

    R*idx 가 32bit 넘어가는데 확인해보세요.


    11년 전 link
  • JongMan
    JongMan

    @xesmaster, 디피는 확인용이고 실제 솔루션은 그밑에 있음 ㅋㅋ


    11년 전 link
  • kwangswei
    kwangswei

    여담이지만 저는 종만님 DP로 검증 + Greedy 로 푸신거보고....털썩....


    11년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.