백준 및 코드포스

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

시험기간이지만 골드 4를 맞춘 것은 대수이고 대사이기에 블로그에 간단히 적겠습니다.

10 20 10 30 20 50​

예제와 같이 이렇게 수열을 입력받았다고 치겠습니다.

그럼 제 코드에 의해서
10 20 10 30 20 50
1 2 1 3 2 4 이렇게 되겠죠?

max값에 가장 큰 값인 4를 저장해서

max가 4인 경우의 값인 50을 brr에 저장, max--
max가 3인 경우의 값인 30을 brr에 저장, max--
max가 2인 경우의 값인 20을....
이렇게 하는 식으로 풀었습니다.

골드 4도 운 좋게 풀었네요!
읽어주셔서 감사합니다

#include <stdio.h>

int main(void) {
    int arr[1002][2];
    int brr[1002];
    int n, a = 0, temp = 0, max = 0, o = 1;;

    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i][0]);
        arr[i][1] = 1;
    }
    if(n == 1) {
        printf("%d\n%d", 1, arr[0][0]);
        return 0;
    }
    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(max < arr[i][1]) {
            max = arr[i][1]; //max는 수열의 길이
        }
    }
    printf("%d\n", max);
    
    for(int i = 1; i <= n; i++) { 
        if(arr[n - i][1] == max) { //가장 긴 증가하는 부분 수열의 길이가 max값과 같다면
            brr[temp] = arr[n - i][0]; //brr[temp]는 가장 긴 증가하는 부분 수열의 값
            max--; //max값은 줄여주고
            temp++; //temp값은 늘려주고
        }
    }
    for(int i = temp - 1; i >= 0; i--) printf("%d ", brr[i]); //거꾸로 저장됐으니 뒤에서부터 출력

    return 0;
}

맞았습니다 뜰 때의 대어를 잡은 기분... 아시나요?

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

안녕하세요. 

제 인생 첫 번째로 백준 골드 문제를 풀었습니다.

어제 프로그래밍 쪽지시험도 분반 1등하고 기분이 좋습니다.

그럼 설명하겠습니다.

n이 1일 경우

1 2 3 4 5 6 7 8 9 10  의 경우가 있는 것까지 계산하고

n이 2일 경우

1 3 6

n이 3일 경우

1 4 10 까지만 계산했습니다.

1 2 3

1 3 6

1 4 10  감이 오시나요?

arr[n][k] = arr[n - 1][k] + arr[n][k - 1] 로 나타나는 것을 알 수 있습니다.

1열은 모두 1입니다. n을 1개의 수로 나타낼 수 있는 방법은 n 밖에 없으니까요.



정수 오버플로우가 날 수 있으니 for문 내부에서 미리미리 나눠줬습니다. 

근데 실버3 dp문제 계단오르기를 못 풀겠네요..

#include <stdio.h>

int main(void) {
    int n, k;
    int arr[201][201];
    scanf("%d %d", &n, &k);
    arr[1][1] = 1;
    for(int i = 2; i < 201; i++) {
        arr[i][1] = 1;
        arr[1][i] = i;
    }
    for(int i = 2; i <= n; i++) {
        for(int j = 2; j <= k; j++) {
            arr[i][j] = (arr[i - 1][j] + arr[i][j - 1]) % 1000000000; 
        }
    }
    printf("%d", arr[n][k]);
}

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

실버 2 찍을겸 빠르게 풀어봤습니다.

코드블럭에 설명을 상세히 적어놨습니다.

감사합니다.

#include <stdio.h>

int main(void) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    for(int i = 0; i < c; i++) { // 입력받은 c만큼 1분씩 더해주는 느낌입니다.
        b++; // c(추가할 분)1분당 b(분)도 1분씩 더해주면서
        if(b == 60) { //b(분)이 60분이 된다면
            a++; //a(시간)을 1 올려주고
            b = 0;//b는 0으로 만들어줍니다.
        }
        if(a == 24) {//a가 24시가 된다면
            a = 0;//a를 0으로 만들어줍니다.
        }
    }
    printf("%d %d", a, b);
}

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