[BOJ] BOJ 32114번 'SoleMap' (Java)

[문제]

https://www.acmicpc.net/problem/32114

 

[접근방식]

도시와 도시 사이에 위치한 각 도로의 '도로 부담' 지수를 구하는 문제이다.

 

1. '차량 정보'를 이용하여 각 도로 구간 별 일일 차량 통행량을 구한다.

2. 각 도로 구간의 차선 개수에 따라 일일 차량 통행량을 최대한 고르게 분배한다.

 

1번과 2번을 구현하는 방식은 크게 어렵지 않았다.

그러나 1번을 단순 구현을 한다면 "시간초과" 에 걸릴 수 있다.

 

※ 배열의 인덱스 편의상 도시의 명칭은 0 부터 N - 1까지 지정한다.

 

1. 단순 누적합 구하기

// 차량 정보 처리
long[] vehicleCount = new long[N]; // 구간 별 차량 수 누적
for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken()) - 1;  // 도시 인덱스 0-based
    int v = Integer.parseInt(st.nextToken()) - 1;
    int x = Integer.parseInt(st.nextToken());
    
    for (int a = u; a < v; a++) {
        vehicleCount[a] += x;
    }
}

단순 누적합을 구하는 방식은 u 구역 부터 v-1 구역까지 반복문을 통해 통행량을 누적하여 계산한다.

 

2. 증감을 이용한 누적합 구하기

// 차량 정보 처리
long[] vehicleCount = new long[N]; // 차량 수 누적
for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken()) - 1;  // 도시 인덱스 0-based
    int v = Integer.parseInt(st.nextToken()) - 1;
    int x = Integer.parseInt(st.nextToken());
    
    vehicleCount[u] += x;  // 구간 시작에 차량 수 추가
    if (v < N) vehicleCount[v] -= x;  // 구간 끝 뒤에 차량 수 빼기
}

// 차량 수를 구간별로 누적
for (int i = 1; i < N; i++) {
    vehicleCount[i] += vehicleCount[i - 1];
}

전 인덱스의 값을 이용하여 해당값으로 부터의 증감값을 이용하여 통행량을 계산한다.

이 방식은 한번의 반복문을 통해 통행량 계산을 완료할 수 있다.

 

[Java 코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 도시의 수 N, 차량 정보의 수 M
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        // 각 도로의 차선 수 w[i]
        int[] w = new int[N - 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N - 1; i++) {
            w[i] = Integer.parseInt(st.nextToken());
        }
        
        // 차량 정보 처리
        long[] vehicleCount = new long[N]; // 차량 수 누적
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()) - 1;  // 도시 인덱스 0-based
            int v = Integer.parseInt(st.nextToken()) - 1;
            int x = Integer.parseInt(st.nextToken());
            
            vehicleCount[u] += x;  // 구간 시작에 차량 수 추가
            if (v < N) vehicleCount[v] -= x;  // 구간 끝 뒤에 차량 수 빼기
        }

        
        // 차량 수를 구간별로 누적
        for (int i = 1; i < N; i++) {
            vehicleCount[i] += vehicleCount[i - 1];
        }
        
        // 도로 부담 계산
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N - 1; i++) {
            long c = vehicleCount[i];  // 도로에 지나가는 차량 수
            int lanes = w[i];  // 차선 수
            
            // 차량 c 대를 lanes 개 차선에 분배
            long quotient = c / lanes;  // 각 차선에 기본적으로 할당되는 차량 수
            long remainder = c % lanes; // 나머지 차량 수
            
            // 분배된 차량 수에 대한 제곱합 최소화
            // remainder 차선에는 (quotient + 1) 대, 나머지 차선에는 quotient 대를 할당
            long weight = remainder * (quotient + 1) * (quotient + 1) + (lanes - remainder) * quotient * quotient;
            sb.append(weight).append("\n");
        }
        
        System.out.print(sb);
    }
}