백준 1286번: 부분 직사각형

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

 

문자로 채워져있는 직사각형 표의 부분 직사각형의 모든 경우의 수에 대해서 모든 알파벳이 몇 번 나오는지 출력하는 문제이다.

처음에는 직사각형을 전부 그려보려 했으나,  1<= n , m <= 50 이라는 범위가 주어져 시간초과가 발생하기 때문에 반려하였다. 대신, 특정 좌표에 있는 문자가 총 몇개의 부분 직사각형에 포함되는지 알면 좋을것 같다는 생각을 하게 되었다. 원래의 직사각형을 이어 붙여 가로, 세로를 두 배로 만든 후, 이 직사각형 내에서 만들 수 있는 모든 가능한 부분 직사각형을 고려할 수 있게 된다. 이때, 확장한 직사각형의 세로는 H, 가로는 W로 정하였다.

 

특정 위치의 문자가 포함되는 경우의 수는 가로, 세로 구간이 해당 위치를 포함해야 한다. 즉, i, j에 대해서 (0~i 구간) * (i~H-1까지 구간) * (0~j 구간) * (j~W-1 구간)을 구하면 된다. 즉,  (i + 1) * (H - i) * (j + 1) * (W - j)이 해당 위치의 문자열의 반복 횟수이다.

for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
        char currentChar = origin[i % N][j % M];
        long contribution = (long) (i + 1) * (H - i) * (j + 1) * (W - j);
        
        alphabetCount[currentChar - 'A'] += contribution;
    }
}

 

 

결과 코드는 다음과 같다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 부분직사각형1286 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken());
        long[] alphabetCount = new long[26];
        
        char[][] origin = new char[N][M];
        for (int i = 0; i < N; i++) {
            origin[i] = br.readLine().toCharArray();
        }
        
        int H = 2 * N, W = 2 * M;
        
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                char currentChar = origin[i % N][j % M];
                long contribution = (long) (i + 1) * (H - i) * (j + 1) * (W - j);
                
                alphabetCount[currentChar - 'A'] += contribution;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            sb.append(alphabetCount[i]).append('\n');
        }
        System.out.print(sb);
    }
}