[C언어] 백준 | 11660번 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

처음에 쉬운 문제인 줄 알고

#include <stdio.h>

int main() {
    int arr[1025][1025];
    int dp, n, m, x1, y1, x2, y2;

    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    for(int i = 0; i < m; i++) {
        dp = 0;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        for(int j = x1; j <= x2; j++) {
            for(int k = y1; k <= y2; k++) {
                dp += arr[j - 1][k - 1];
            }
        }
        printf("%d\n", dp);
    }
}

이렇게 제출했더니 시간 초과가 떴습니다.

저는 여태 시간제한이 1초라면 입력 1개당, 그러니까 두 번째 for문 돌면서 i가 ++ 될 때마다 1초인 줄 알았더니, 10만 가지 m이 다 검산될 때까지 1초였습니다.

아무튼 dp문제가 아닌 거 같은데 이게 dp에 실버 1이나 될 문제인가? 하고 제출했다가 시간초과를 받고 코드를 다시 짰습니다.

너무 귀찮았습니다. 

이런게 빡구현인가요? 빡구현이 뭔지를 몰라서..

 

아무튼 보시면 첫 번째로 arr에 값을 넣어줄 때도, 마지막에 값을 출력해줄 때도 배열에서 - 값을 참조하지 않도록 신경 써줘야 합니다.

 

와 생각해보니까 처음부터 배열 크기를 크게 잡고 i랑 j를 1로 두고 시작했어도 됐겠네요??

 

하단의 첫 번째 코드블럭은 제가 깨달음을 얻고 바꾼 것이구요,

하단의 두 번째 코드블럭은 미련하게 하나하나 경우의 수를 따져가며 짠 코드입니다.

 

아무튼 뭐 사고력이 늘었다면 ok 아닐까요?

#include <stdio.h>

int main() {
    int arr[1026][1026];
    int dp, n, m, x1, y1, x2, y2;

    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%d", &dp);
                arr[i][j] = dp + arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1]; 
        }
    }
   for(int i = 0; i < m; i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
                printf("%d\n", arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] + arr[x1 - 1][y1 - 1]); 
    }
}

하단의 코드는 참고 안 하셔도 됩니다.

#include <stdio.h>

int main() {
    int arr[1025][1025];
    int dp, n, m, x1, y1, x2, y2;

    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%d", &dp);
            if (i == 0 && j == 0) { //arr[0][0]일 때
                arr[i][j] = dp;
            }
            else if(i == 0 && j != 0) { //arr[0][n]일 때
                arr[i][j] = dp + arr[i][j - 1]; 
            }
            else if(i != 0 && j == 0) { //arr[n][0]일 때
                arr[i][j] = dp + arr[i - 1][j]; 
            }
            else if(i != 0 && j != 0) { //arr[n][n]일 때
                arr[i][j] = dp + arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1]; 
            }
        }
    }
   for(int i = 0; i < m; i++) {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        if (x1 == 1 && y1 == 1) {
                printf("%d\n", arr[x2 - 1][y2 - 1]);
            }
            else if(x1 != 1 && y1 == 1) {
                printf("%d\n", arr[x2- 1][y2 - 1] - arr[x1 - 2][y2 - 1]); 
            }
            else if(x1 == 1 && y1 != 1) {
                printf("%d\n", arr[x2 - 1][y2 - 1] - arr[x2 - 1][y1 - 2]); 
            }
            else if(x1 != 1 && y1 != 1) {
                printf("%d\n", arr[x2 - 1][y2 - 1] - arr[x1 - 2][y2 - 1] - arr[x2 - 1][y1 - 2] + arr[x1 - 2][y1 - 2]); 
            }
    }
}