SWEA[8275] - 햄스터[D4]

링크

SWEA[8275]

문제설명

• 완전탐색

문제풀이

• serial의 합이 큰 것
• 최종 조건이 사전순서이므로 0~X로 serial를 만드는게 맞다.

문제코드

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

public class Solution8275 {

    public static int N;
    public static int X;
    public static int M;

    public static int[] Ans;
    public static int[] serial;
    public static int[][] oper;
    public static int serial_sum;
    public static int ans_sum=Integer.MIN_VALUE;

    public static boolean is_ok(int oper_idx) {
        int sum=0;
        for (int i = oper[oper_idx][0]; i <= oper[oper_idx][1]; i++) {
            sum+=serial[i];
        }

        if(sum==oper[oper_idx][2]) {
            return true;
        }
        else {
            return false;
        }
    }

    public static void DFS(int cnt) {
        if(cnt==N) {
//            serial이 생성됨
//            System.out.println(Arrays.toString(serial));
            for (int i = 0; i < M; i++) {
                if(!is_ok(i)) {
                    return;
                }
            }
//            햄스터 갯수 만족할 때,
            serial_sum=0;
            for (int i = 0; i < N; i++) {
                serial_sum+=serial[i];
            }
            if(ans_sum < serial_sum) {
                ans_sum=serial_sum;
                Ans = Arrays.copyOf(serial, N);
            }
            return;
        }

        for (int i = 0; i <= X; i++) {
            serial[cnt]=i;
            DFS(cnt+1);
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/8275.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());
            X = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            Ans = new int[N];
            Ans[0]=-1;
            serial = new int[N];
            oper = new int[M][3];
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                oper[i][0] = Integer.parseInt(st.nextToken())-1;
                oper[i][1] = Integer.parseInt(st.nextToken())-1;
                oper[i][2] = Integer.parseInt(st.nextToken());
            }

            DFS(0);

            System.out.print("#"+test_case+" ");

            if(Ans[0]==-1) {
                System.out.println(-1);
            }
            else {
                for (int i = 0; i < N; i++) {
                    System.out.print(Ans[i]+" ");
                }
                System.out.println();
            }
//            초기화
            ans_sum = Integer.MIN_VALUE;
        }
    }
}

아쉬운점

• 햄스터 갯수 세아리고 판단하는 메서드 만들 때, 합 비교하는 변수 잘못넣음.
• ans_sum 초기화 안함

잘한점

• O(N)
  • (Serial경우의수) * 조건검사 = 11^6 * 6* 10 = 10^8
  • 시간초과 안됨
• 조건 고려 다함.