Codeforces 1143B. Saving the City

1143B. Saving the City

n개의 빌딩이 있다. 이때 몇몇 빌딩의 밑에 광산이 존재하며 이를 활성화 하기 위해서는 a비용이 필요하다. 또한 x번 빌딩의 광산을 활성화 하면 인접해 x-1, x+1의 광산들을 모두 활성화할 수 있다. 비용을 줄이기 위해 특정 빌딩에 b비용을 추가하여 광산을 만들 수 있다고 할 때 모든 광산을 활성화 하기 위해서 드는 최소 비용을 구하는 문제이다.

이 문제는 빌딩의개수 x 2 크기의 배열을 이용하여 문제를 해결할 수 있다. 첫 번째 원소는 해당 빌딩의 광산을 활성화 하지 않는 최소 값이며 두 번째 원소는 해당 빌딩의 광산을 활성화 하는데 최소 값이다.

import java.io.*;
import java.util.StringTokenizer;

public class Main{
    public static void main(String [] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(br.readLine());
        while(tc-- != 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            String building = br.readLine();
            int len = building.length();
            final int maxVal = (a + b) * len;
            // 0 : 밑에 광산이 없는 것, 1 : 밑에 광산이 있는 것
            int [][] dp = new int[len][2];
            for(int i = 0; i<len; i++){
                if(building.charAt(i) == '0'){
                    dp[i][0] = (i > 0 ? Math.min(dp[i-1][0], dp[i-1][1]) : 0);
                    dp[i][1] = (i > 0 ? Math.min(dp[i-1][0] + a + b, dp[i-1][1] + b) : (a + b));
                }else{
                    dp[i][0] = maxVal;
                    dp[i][1] = (i > 0 ? Math.min(dp[i-1][0] + a, dp[i-1][1]) : a);
                }
            }
            bw.write(Math.min(dp[len - 1][0], dp[len - 1][1])+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}