<aside> 1️⃣

문제: 1449번 수리공 항승

테이프로 물이 새는 위치 좌우 0.5만큼을 막으려고 함

물이 새는 곳의 위치와 테이프 길이 L이 주어졌을 때 필요한 테이프 최소 개수 구하기

</aside>

#include <stdio.h>
#include <stdlib.h>

//비교함수
int compare(const void *a, const void *b){
    return *(int *)a - *(int *)b;
}

int main(){
    int N, L;
    scanf("%d %d", &N, &L);
    int arr[1001];
    
    for(int i = 0; i < N; i++){
        scanf("%d", &arr[i]); //위치 입력받기
    }

    //위치 정렬
    qsort(arr, N, sizeof(int), compare); //순서대로 정렬
    
    int count = 0; //테이프 수 
    double end = 0.0; //테이프 끝

    for (int i = 0; i < N; i++) {
        //현재 테이프 범위 안에 있으면 건너뜀
        if (arr[i] <= end) continue;

        //새 테이프
        count++;

        //왼쪽 0.5부터 덮기 시작. L 길이 덮음
        end = arr[i] - 0.5 + L;
    }

    printf("%d", count);
}

image.png

<aside> 2️⃣

문제: 1904 01타일 00 타일과 1 타일로 N자리 2진수를 만들려고 함

만들 수 있는 길이가 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력..?

</aside>

#include <stdio.h>

#define MOD 15746

int main() {
    int N;
    scanf("%d", &N);

    int dp[1000001];  //최대
    dp[1] = 1;
    dp[2] = 2;

    //피보나치 수열 변형
    //맨 앞 1 나머지는 길이 N-1짜리 수열
    //맨 앞 00 나머지는 길이 N-2짜리 수열
    for (int i = 3; i <= N; i++) {
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;
    }

    printf("%d", dp[N]);
    return 0;
}

image.png