[자바/완전탐색] CodeTree. 밭의 넓이를 고르게 하기

입력 조건이 아래와 같으므로 완전탐색을 하기에 충분하였다.

• 1 ≤ N,H ≤ 100
• 1 ≤ T ≤ min(N,10)
• 0 ≤ 밭의 높이 ≤ 200

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;

public class Main {
    private static int[] arr;
    private static int[] ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        ans = new int[n-t + 1];
        /*
        arr에는 땅의 높이가 저장되어 있음
        Math.abs(arr[i] - h) 를 이용하여 비용을 계산 -> 각 구간별로 비용의 총 합을 ans[]에 입력
        윈도우의 길이는 t

        for i in range(0, n-t):
            for j in range(0, t):
                ans[i] += Math.abs(arr[i+j] - h);
        **/
        for (int i = 0; i < n - t + 1; i++) {
            for (int j = 0; j < t; j++) {
                ans[i] += Math.abs(arr[i + j] - h);
//                System.out.println("ans[i] = " + ans[i] + " || " + i);
            }
        }
        int res = Arrays.stream(ans).min().orElseThrow(() -> new NoSuchElementException(""));
        System.out.println(res);

    }
}

 

위보다 효율적으로 짜기 위해선, ans배열에 값을 저장해두고 나중에 최소값을 계산해보기보단 min값만 계속 연산하면서 찾아두면 된다.

/*해답*/
import java.util.Scanner;

public class Main {
    public static final int INT_MAX = Integer.MAX_VALUE;
    public static final int MAX_N = 100;
    
    public static int n, h, t;
    public static int[] arr = new int[MAX_N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 입력
        n = sc.nextInt();
        h = sc.nextInt();
        t = sc.nextInt();
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        
        // 모든 구간의 시작점을 잡아봅니다.
        int minCost = INT_MAX;
        for(int i = 0; i <= n - t; i++) {
            // 해당 구간을 고르게 할 때의 비용을 구합니다.
            int cost = 0;
            for(int j = i; j < i + t; j++)
                cost += Math.abs(arr[j] - h);
            
            // 최솟값을 구합니다.
            minCost = Math.min(minCost, cost);
        }
                            
        System.out.print(minCost);
    }
}

 

교훈 :

슬라이딩 윈도우 활용시, 전체 길이가 n이고 윈도우 크기가 t이면 그 경우의 수는 n - t + 1이 된다.