[백준 / BOJ] 23247 Ten (Java)

문제 

출처 : https://www.acmicpc.net/problem/23247

23247번: Ten

N*M그리드에서 A*B범위의 사각형을 만들때, 그 사각형 범위안에 포함된 원소의 합을 10으로 만드는 사각형 범위의 갯수를 찾는 문제다.

 

---

풀이

어려워? 보이지만 원소의 합을 10으로 만들어야하고, N*M그리드에서 가장 작은 원소의 값은 1이므로, 사각형의 최대 증가 범위는 10이 된다. 따라서, 완전탐색으로 풀어도 풀린다.

 

시간복잡도를 계산해보면, 

1) 가능한 사각형 범위의 종류 = 33개

2) N*M에서 모든 경로를 최대로 보는 경우 = 300*300 = 90,000 번(실제로는 아무리 최악의 경우로 가도 이거보다 적다.)

3) 매 탐색마다 사각형 범위안에 포함된 원소의 합을 구하는 연산 = 10번

최종 연산횟수 = 900,000 * 33 = 29,700,000

따라서, 시간복잡도만 보면 일반적인 완전탐색으로도 풀려야 하는데, 나는 시간초과가 나와서 누적합을 추가해 3번 연산을 O(1)로 줄여 풀어줬다.

 

알고리즘은 다음과 같다.

1. N*M그리드에 대해서 2차원 누적합을 만든다.

    private void initCum(){
        landCum[0][0] = land[0][0];
        for(int i = 1; i < N; i++) landCum[i][0] = landCum[i-1][0] + land[i][0];
        for(int j = 1; j < M; j++) landCum[0][j] = landCum[0][j-1] + land[0][j];
        for(int i = 1; i < N; i++)
            for(int j = 1; j < M; j++)
                landCum[i][j] = land[i][j] + landCum[i][j-1] + landCum[i-1][j] - landCum[i-1][j-1];
    }

2. 만들 수 있는 사각형 범위를 만들어준다. (1*1 범위의 사각형 부터 1*10, 10*1 범위의 사각형까지)

    private int findSubsections(){
        int subsections = 0;
        for(int height = 0; height <= 10; height++)
            for(int width = 0; width <= 10 && width*height <= 10; width++)
                subsections += findSubsections(0,0, height, width);
        return subsections;
    }

3. 0,0번부터 y+height, x+width 가 범위에 포함될때까지 y,x를 각각 1씩 증가하며 모든 경우를 탐색한다.

    private int findSubsections(int y, int x, int height, int width){
        if(y + height >= N) return 0;
        if(x + width >= M) return findSubsections(y+1, 0, height, width);
        int sectionWeight = getSectionWeight(y, x, height, width);
        int ans = 0;
        if(sectionWeight == 10) ans++;
        return ans + findSubsections(y, x+1, height, width);
    }

4. 사각형 범위에 포함된 원소의 합이 10인지 확인한다. 이 과정을 누적합을 이용해 O(1)로 줄여줘야한다.

    private int getSectionWeight(int y, int x, int height, int width){
        int sectionWeight = landCum[y+height][x+width];
        if(y-1 >= 0) sectionWeight -= landCum[y-1][x+width];
        if(x-1 >= 0) sectionWeight -= landCum[y+height][x-1];
        if(y-1 >= 0 && x-1 >= 0) sectionWeight += landCum[y-1][x-1];
        return sectionWeight;
    }

그리 어렵지 않은 문제였는데, 누적합을 사용하지 않고 구현하다가 틀려서 시간이 좀 오래걸렸다. 

---

 

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/23247%20Ten/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃