백준 및 코드포스

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

처음에 쉬운 문제인 줄 알고

#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]); 
            }
    }
}

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

안녕하세요.

i와 j에 임의의 값을 브루트포스로 넣어주면서 d일의 피보나치 수가 처음 입력한 k의 값과 맞는지 확인만 해주면 되는 간단한 문제입니다.

#include <stdio.h>

int main(void) {
    int d, k;
    int arr[31];
    scanf("%d %d", &d, &k);
    for(int i = 1; i < k; i++) {
        arr[0] = i;
        for(int j = 1; j < k; j++) {
            arr[1] = j;
            for(int l = 2; l < d; l++) { //d일의 피보나치 수를 구함.
                arr[l] = arr[l - 1] + arr[l - 2];
            }
            if(arr[d - 1] == k) { //d일의 피보나치 수와 k가 일치한다면
                    printf("%d\n%d", i, j); // arr[0], arr[1]을 출력
                    return 0;
            }
        }
    }
}

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

안녕하세요.

제가 많이 풀어봤던 dp 종류의 문제입니다.

더했을 때 최고의 값만을 dp에 저장해주면서 배열을 진행해주면 쉽게 풀 수 있습니다.

if문을 쓴 것은 만약 i 나 j 가 0인데 배열상 -1을 시켜서 불러오려고 하면 배열에 오류가 생길 것 같아서 i와 j가 각각 0일 경우와 둘 다 0인 경우를 if문을 사용해서 나눠줬습니다.

하단에 if문을 쓰지 않았을 때 -1 배열을 참조하는 경우의 코드도 넣어놨으니 참고하시면 될 듯합니다.

질문은 댓글로 부탁드립니다.

#include <stdio.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int main(void) {
    int n, m;
    int arr[301][301];
    int dp[301][301];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(i != 0 && j != 0)
                dp[i][j] = MAX(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]);
            else if(i == 0 && j != 0) {
                dp[i][j] = dp[i][j - 1] + arr[i][j]; // 첫번째 행일 경우
            }
            else if(i != 0 && j == 0) {
                dp[i][j] = dp[i - 1][j] + arr[i][j]; // 첫번째 열일 경우
            }
            else if(i == 0 && j == 0) {
                dp[i][j] = dp[i][j] + arr[i][j]; //배열 [0][0]인 경우
            }

        }
    }
    printf("%d", dp[n - 1][m - 1]);
}

#include <stdio.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int main(void) {
    int n, m;
    int arr[301][301];
    int dp[301][301];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
                dp[i][j] = MAX(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]);
        }
    }
    printf("%d", dp[n - 1][m - 1]);
}

dp[-1][0] 혹은 dp[0][-1] 혹은 dp[-1][-1] 등의 값을 비교할 수도 있는 경우. 

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

쉬운 문제인데 맨 처음에 삼각형 경로를 비교할 때 j값을 j < i로 두고 뭐가 틀렸나 한참 찾았습니다.

주석처리 한 부분은 제대로 잘 더해지고 있는지 확인하기 위한 코드로, 만약 이 글을 읽고 계신 분이 자신의 코드가 잘 작동하지 않는다고 느끼신다면 주석 부분을 긁어서 밑에 넣고 같이 실행시켜보세요. 

뭐가 틀린지 알 수 있을 겁니다.

#include <stdio.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int main(void) {
    int n;
    int arr[510][510];
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= n - i; j++) {
            arr[n - i - 1][j] += MAX(arr[n - i][j], arr[n - i][j + 1]); // (바로 밑과 우측 대각선 비교하여 큰 값 올림)
        }
    }
/*        for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }*/
        printf("%d", arr[0][0]); //최상단 (가장 큰 값 출력)
}

아까운 30분....