백준 및 코드포스

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

안녕하세요, 골드 3을 우연찮게 풀게 됐습니다. 투포인터를 배우자마자 처음으로 푼 문제입니다.

연속합 문제라 투포인터를 사용하면 쉽게 풀 수 있는 문제인데, 에라토스테네스의 체를 사용해야 합니다. 

왜냐면 소수의 연속합 문제이기 때문이죠. 

에라토스테네스의 체는 예전에 풀어봐서 구현은 쉽게 했습니다.

하지만 문제가 있었습니다. N이 400만이었기 때문인데요, 지역 변수로 400만개짜리 배열을 선언했더니 zsh segmentation fault였나? 오류가 떴습니다. 100만 정도까진 괜찮았는데 좀 커지면 계속 오류가 뜨더라고요.

그래서 전역 변수로 배열을 선언해줌으로써 문제를 해결했습니다. 하지만 고작 그것 하나 해결하는 데에 20분 가까이 썼다는 점이 아쉬웠습니다.

하지만 지식을 얻었다는 것.

그렇다면 오케이겠죠?

brr의 사이즈가 283148인 이유는 1~400만 사이의 소수의 개수가 283148개였나? 그쯤이길래 저렇게 했습니다.

#include <stdio.h>
#include <math.h>

#define S 4000001 //배열 크기
int arr[S] = {0};

int main(void) {
    int brr[283148];
    int n = 1, N;
    int a = 1, b = 2, temp, answer = 0;
    scanf("%d", &N);

    for(int i = 2; i < sqrt(S); i++) { //에라토스테네스의 체
        if(arr[i] != 1) {
            for(int j = 2; i * j < S; j++) {
                arr[i * j] = 1;
            }
        }
    }
    for(int i = 2; i <= S; i++) { //소수를 brr로 옮기기
        if(arr[i] != 1) {
            brr[n] = i;
            n++;
        }
    }
    temp = brr[1];
    for(int i = 1; i < 283148 * 2; i++) { //여기서부터 투포인터 입니다.
        if (temp < N) {
            temp += brr[b];
            b++;     
        }
        else if(temp > N) {
            temp -= brr[a];
            a++;    
        }
        else if(temp == N) {
            answer++;
            temp += brr[b];
            b++;   
        }
        if(brr[b - 1] > N) break;
    }
    printf("%d", answer);
}

400만을 여러 번 적으려니까 귀찮아져서 define 사용해봤습니다. 

하하하 감사합니다

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