백준 및 코드포스

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분....

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

거의 한 시간 정도 걸린 것 같습니다.

dp배열을 새로 주는 것보다 기존의 숫자가 들어가 있는 배열을 2차원으로 줘서 옆에다 메모하며 푸는 느낌으로 하고 싶어서 arr 배열을 2차원으로 줬습니다. 그러니까 arr[i][0]에는 숫자가, arr[i][1]에는 해당 숫자가 몇번째 배열인지 적혀있는 식입니다.

scanf로 받아주면서 숫자 하나만 있어도 배열의 길이는 1이니까 

arr[i][1] = 1; 넣어줬습니다.

궁금한게 있다면 댓글로 남겨주세요.

감사합니다.

#include <stdio.h>

int main(void) {
    int arr[1001][2];
    int n, a = 0;

    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i][0]);
        arr[i][1] = 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            if(arr[i][0] > arr[i - j][0] && arr[i][1] <= arr[i - j][1]) {
                arr[i][1] = arr[i - j][1] + 1;
            }
            if(arr[i][0] == arr[i - j][0] && arr[i][1] <= arr[i - j][1]) {
                arr[i][1] = arr[i - j][1];
            }
        }
    }
    for(int i = n - 1; i > 0; i--) {
        if(arr[i][1] > arr[i - 1][1]) {
            arr[i - 1][1] = arr[i][1]; //최댓값을 arr[0][1]로 끌어오기
        }
    }
    printf("%d", arr[0][1]);
    return 0;
}