백준 및 코드포스

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

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

안녕하세요.

단계별로 풀기 들어와봤는데 1단계 마지막 문제를 안 풀어놨길래 빠르게 풀어봤습니다.

아주 간단하니 코드만 보여드리도록 하겠습니다.

나누기 10, 나누기 100 하는 이유는 잘 아시겠죠?

#include <stdio.h>

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);

    int one = m % 10; // 1의 자리
    int ten = m % 100 - one; //10의 자리
 
    printf("%d\n", one * n); // 1의 자리 * n
    printf("%d\n", (ten * n) / 10); //10의 자리 * n
    printf("%d\n", ((m - ten - one) * n) / 100);// 100의 자리 * n
    printf("%d", n * m);
    
    return 0;
}

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

2종류인데 1짝을 뽑으려면 사진처럼 3개를 뽑으면 됩니다.

2종류인데 2짝을 뽑는 최악의 상황은 5개를 뽑을 때 입니다.

n종류일 때 r짝은

n + 2 * r - 1

입니다.

#include <stdio.h>

int main() {
    long long n, r;
    scanf("%lld%lld", &n, &r);
    printf("%lld", n + 2 * r - 1);
}

짧아서 재밌어서 올려봤습니다.

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

안녕하세요. 황지원입니다.

dp를 그제 처음 배워가지고 dp문제를 중점으로 한동안 풀어볼 생각입니다.

서울대학교, 부산대학교 분에게 백준 문제를 풀 거라면 c++을 하라고 추천받았습니다. 실버 3에서 실력이 멈춘 것 같았는데, 알고 보니 문제를 풀려면 언어 공부가 아닌 알고리즘 공부를 해야 하더라고요. dp 공부하고 바로 실버 1문제를 풀 수 있게 되었습니다. 물론 운이 따라줬지만요.
아무튼 c++을 추천받았습니다만, 제가 현재 c언어 수업을 듣고 있거든요.
둘이 아예 다른 언어이면 상관이 없습니다. 하지만 비슷한 언어라서 제가 헷갈릴까봐 걱정이 되어 둘이 같이는 못 배울 듯합니다.

아무튼 그래서 정렬 등과는 다르게 c언어로 아주 쉽게 구현이 가능한 다이나믹 프로그래밍 문제를 풀 생각입니다.
근데 피보나치 문제와는 다르게 제가 오늘 푼 것도 dp의 범주에 들어가는지는 모르겠네요.
사족이 길었네요.

시작하겠습니다.

1을 입력받았을 때를 생각해보면
0 1 2 3 4 5 6 7 8 9
모두 오르막 수임을 알 수 있습니다.

맞죠?

2를 입력받아서 이제 0~9의 뒤에 숫자를 하나씩 덧붙여 오르막 수를 만든다고 가정을 해봅시다.
9의 뒤에는 1개의 수만 올 수 있습니다. 9이죠.
8의 뒤에는 2개의 수가 올 수 있습니다. 8, 9 입니다.
7의 뒤에는 3개
6의 뒤에는 4개
.
.
.
0의 뒤에는 10개의 수가 올 수 있습니다. (0부터 9까지 모두 가능하니까요.)

제가 여기까지만 하고 어떻게 풀어야하나 고민을 했는데요, 여기에 규칙이 있습니다.

2를 입력받아서 만들어진 오름 수를 보면,
0으로 끝나는 수는 1개뿐입니다. 00이죠.
1로 끝나는 수는 2개입니다. 01과 11이죠.
2로 끝나는 수는 3개입니다. 02, 12, 22.
3으로 끝나는 수는 4개입니다.
.
.
9로 끝나는 수는 10개입니다. 09, 19, 29, 39, 49, 59, 69, 79, 89, 99

3을 입력받아서 위에서 만들어진 오름수의 뒤에 숫자를 덧붙여봅시다.

0으로 끝나는 수는 또 1개뿐이겠죠? 000
1로 끝나는 수는 3개입니다. 001, 011, 111
2로 끝나는 수는 6개입니다. 002, 012, 112, 022, 122, 222

규칙성을 찾으셨나요?

일단 0으로 끝나는 수는 1개밖에 만들어질 수 없습니다.
그리고 3번째에서
1로 끝나는 수는 2번째에서 기존에 1로 끝나는 수 01, 11과 1보다 작은 숫자인 0으로 끝났던 00을 더해 3개입니다.
2로 끝나는 수는 2번째에서 기존에 2로 끝났던 02, 12, 22와 00, 01, 11가 2로 끝날 수 있으니 6개이죠.
3으로 끝나는 수는 4 + 3 + 2 + 1로 10입니다.
4로 끝나는 수는 5 + 4 + 3 + 2 + 1로 15
.
.
.
9로 끝나는 수는 10 + 9 + .. + 1 로 55개입니다.
제가 한 말을 이해하셨다면
arr[0] = 1;
arr[i] = arr[i - 1] + arr[i];
이 부분을 이해하실 겁니다.

추가적으로 미리미리 10007로 나눠놔야 정수 오버플로우가 생기지 않겠죠?
이걸 푸시는 분들이라면 다 알고 계실 거라고 생각합니다.

제 첫 실버 1 문제였습니다.
블로그 만든 지 얼마나 됐다고 검색해서 들어오는 분들이 계셔서 열심히 적어봤습니다.
문제 푸는데 8분, 블로그에 적는데 30분 걸렸습니다.

감사합니다.

#include <stdio.h>

int main(void) {
    long long arr[11] = {1,2,3,4,5,6,7,8,9,10};
    int n;
    int m = 0;
    scanf("%d", &n);
    if(n == 1) {
        printf("10");
        return 0;
    }
    for(int j = 0; j < n - 2; j++) {
    for(int i = 1; i < 10; i++) {
        arr[0] = 1;
        arr[i] = (arr[i - 1] + arr[i]) % 10007;
    }
    }
    for(int i = 0; i < 10; i++) {
        m += arr[i];
    }
    m %= 10007;
    printf("%d", m);
    return 0;
}