SWEA[2115] - 벌꿀 채취

링크

SWEA[2115]

문제설명

• 완전탐색

문제풀이

• 완전탐색 + 최대값 찾기

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Solution2115 {

//    초기입력
    public static int Ans=Integer.MIN_VALUE;
    public static int N;
    public static int M;
    public static int C;
    public static int[][] map;
//    벌꿀채취최대값
    public static int get=0;
    public static int score=0;
    public static int Ans_score=Integer.MIN_VALUE;
    public static int Temp;

    public static void Max(int[] rc, int cnt) {
        if(cnt==M) {
            Ans_score = Math.max(Ans_score, score);
            return;
        }
        for (int i = 0; i < 2; i++) {
            get += i*map[rc[0]][rc[1]+cnt];
            score += i*map[rc[0]][rc[1]+cnt]*map[rc[0]][rc[1]+cnt];
//            벌꿀 양 초과안하면
            if(get<=C) {
                Max(rc,cnt+1);
            }
//            초과했으면 가지치기
//            원상복구
            get -= i*map[rc[0]][rc[1]+cnt];
            score -= i*map[rc[0]][rc[1]+cnt]*map[rc[0]][rc[1]+cnt];
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/2115.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {

            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            map = new int[N][N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N-M+1; j++) {    //N=4 , C=2 이면 (0,2)까지만 가능 (0,3)는 설치불가
                    for (int i2 = i; i2 < N; i2++) {
                        for (int j2 = 0; j2 < N-M+1; j2++) {
//                            일꾼 경로가 겹치는 경우
                            if(i==i2 && j+M>j2) {
                                continue;
                            }
                            else {
                                Temp=0;
//                                첫번째 일꾼
                                get=0;
                                score=0;
                                Ans_score=0;
                                Max(new int[] {i,j},0);
                                Temp+=Ans_score;
//                                두번째 일꾼
                                get=0;
                                score=0;
                                Ans_score=0;
                                Max(new int[] {i2,j2},0);
                                Temp+=Ans_score;
//                                최대값 갱신
                                Ans = Math.max(Ans, Temp);
                            }
                        }
                    }
                }
            }

            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=Integer.MIN_VALUE;
        }//end test_case
    }//end main
}

아쉬운점

• 인덱싱 실수함
  • j 범위를 채취가능 칸수인 M을 이용해서 N-M+1로 해야하는데
  • 채취가능량인 C로 N-C+1로 해서 답이 안나왔음.
• 재귀로 완전탐색 돌릴 때 원상복구할때 빼줘야하는데 더해줬었음

잘한점

• O(N)계산
  • (N^2)C2 * 2^M = 5000*32 = 16000 안터짐
• 일꾼 설치를 재귀로 짜려고하다가 굳이 그렇게 안짜도 될 것 같아서 그냥 4중for문 돌렸음
• 일꾼 설치했을 경우, 최대 score 찾는것은 완전탐색으로 돌림
• 빨리함 (35분)