[SWEA] 3813. 그래도 수명이 절반이 되어서는...

[SWEA] 3813. 그래도 수명이 절반이 되어서는...

Problem

제출일 : 2019-12-11

문제 풀이 시간 : 1H 45M

난이도 : ★★★★

---

link : https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxo6c6AVkDFAW4#

삼성전자에서 생산하는 플래시 드라이브를 포맷하는 프로그램을 작성하려고 한다.

드라이브를 포맷할 때 특정한 초기 데이터를 항상 드라이브에 저장해 두어야 한다. 이 데이터는 매우 자주 엑세스되는 종류라서 이 데이터가 저장된 블록은 수명이 짧아질 수 있다.

플래시 드라이브는 N개의 블록으로 구성된 것으로 생각하고 각 블록은 1부터 N까지 번호가 붙은 것으로 생각하자.

각 블록마다 지금까지 얼마나 많은 엑세스가 있었는지 알고 있어서 i번째 블록이 얼마나 닳았는지(Wear Level)를 표현하는 값 W를 모든 블록에 대해 가지고 있다고 한다.

Wi의 값은 1 이상 200,000 이하의 자연수 값이고, 값이 클수록 닳은 정도가 많아서 남은 수명이 짧다는 의미이다.

초기 데이터를 아무 곳에나 저장한다면 플래시 드라이브의 수명이 아주 작아질 수 있을 것이다.

“그래도 수명이 절반이 되어서는” 안된다는 정책에 따라서 초기 데이터를 플래시 드라이브의 적절한 위치에 배치하여 드라이브 수명을 최대한 길게 하고 싶다.

초기 데이터는 K개의 덩어리로 구성되어 있고, 이들 중 i번째 덩어리는 Si개의 연속된 블록에 저장되어야 한다.

또, 덩어리들은 입력에 주어진 순서대로 작은 번호의 블록부터 저장되어야 한다.

또, 하나의 덩어리가 저장된 블록에는 다른 덩어리를 저장할 수 없다.

위의 예는 플래시 드라이브 블록들의 Wear Level을 표시한 것이다.

초기 데이터가 3개의 덩어리로 구성되어 있고 각 덩어리의 블록 수가 2, 1, 3이라고 하면 다음과 같이 저장했을 때 최대 Wear Level이 3이 되어 최적이 된다.

입력으로 플래시 메모리의 블록 수 N, 각 블록의 Wear Level 값, 초기 데이터의 덩어리 수와 각덩어리가 차지하는 블록 수를 받아서 위의 조건을 만족하도록 저장할 때

가능한 최대 Wear Level의 최소값을 구하는 프로그램을 작성하라.

Constraints

1. 플래시 드라이브의 블록 수 N은 최대 200,000이다. (1≤N≤200,000)

2. 각 블록의 Wear Level 값은 1 이상 200,000이하의 자연수이다. (1≤Wi≤200,000)

3. 초기 데이터의 덩어리 수 K는 1 이상 N 이하이다. (1≤K≤N)

4. 초기 데이터의 덩어리 당 블록 수의 합은 1 이상 N 이하이다. (1≤S1+S2+…+SK≤N)

input

첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 50)

그 다음 줄부터는 각 테스트 케이스가 주어지며 각 테스트 케이스의 첫째 줄에는 N과 K의 값이 순서대로 주어진다.

다음 줄에는 W1, W2, …, WN이 순서대로 주어진다.

그 다음 줄에는 S1, S2, …, SK가 순서대로 주어진다.

Output

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, 초기 데이터가 저장된 블록들의 최대 Wear Level의 가능한 최소값을 출력한다.

Example

input

3
9 3
5 2 3 6 1 4 1 3 2
2 1 3
9 2
1 2 3 4 5 6 7 8 9
2 3
9 2
1 2 3 4 5 4 3 2 1
2 3

output

#1 3
#2 5
#3 3

Solution & Inpression

입력이 가능한 최대 N은 200,000이다. 따라서 모든 경우의 수를 탐색하여 답을 구하는 방법으론 문제해결이 불가능한 문제이다.

일반 문제를 결정문제로 바꾸어 생각하여 문제를 풀어야 한다.

거꾸로 생각하는 것으로

답을 X라고 가정했을때 X가 답인 경우엔 X보다 큰 값은 모두 답이고, X가 답이 아닌 경우는 X보다 작은 값은 모두 답이 될 수 없다.

이런 아이디어를 갖고 문제를 접근한다면 보다 쉽게 문제를 해결할 수 있다. 이분탐색을 이용하여 범위를 계속 좁히며 $O(logN)$번의 탐색으로 최종해를 찾을 수 있다.

답이 가능한 경우와 답이 불가능한 경우는 어떻게 확인을 해야할까???

문제에서 입력으로 K개의 덩어리의 블록 수가 들어오는데 이를 배열S에 저장하고

입력받은 배열W를 순회하며 적합성을 파악한다.

Code

언어 : JAVA

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {
    final static int Max = 200009;
    static int[] W = new int[Max], S = new int[Max];
    static int N, K;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            K = sc.nextInt();

            for (int i = 1; i <= N; i++)
                W[i] = sc.nextInt();
            for (int i = 1; i <= K; i++)
                S[i] = sc.nextInt();

            int s = 1, e = Max, m;
            while (s < e) {
                m = (s + e) / 2;
                if (isAvailable(m))
                    e = m;
                else
                    s = m + 1;
            }
            System.out.println("#" + tc + " " + s);
        } // end of TC
        sc.close();
    }// end of Main

    private static boolean isAvailable(int p) {
        int i, now = 1, cont = 0;
        for (i = 1; i <= N; ++i) {
            if (W[i] <= p)
                cont++;
            else
                cont = 0;
            if (cont == S[now]) {
                cont = 0;
                if (++now > K)
                    break;
            }
        }
        return now > K;
    }

}