[SISS/C언어 스터디] 여름 8주차 스터디

여름 8주차 스터디

백준 제출 내역 화면 캡쳐

자율 2문제를 풀어서 제출하면 됩니다.

언어는 C언어만 가능합니다.

레벨 제한사항: Bronze 3 이상

 

2630

---

• 분할 정복 → 종이를 4등분 해 칸 안의 색이 모두 같아질 때까지 반복

// 2630.c

#include <stdio.h>

// 종이 크기, 색종이, 흰 종이 수, 파란 종이 수
int n;
int paper[128][128];
int white = 0;
int blue = 0;

// 종이 나누기
void divide(int x, int y, int size)
{
    int i, j;
    int w = 0;
    int b = 0;

    for (i = x; i < x + size; i++)
    {
        for (j = y; j < y + size; j++)
        {
            // 흰색일 경우 w 증가
            if (paper[i][j] == 0)
            {
                w++;
            }
            // 파란색일 경우 b 증가
            else
            {
                b++;
            }
        }
    }

    // 모두 흰색
    if (w == size * size)
    {
        white++;
    }
    // 모두 파란색
    else if (b == size * size)
    {
        blue++;
    }
    // 섞인 경우 나눠서 재귀
    else
    {
        divide(x, y, size / 2);
        divide(x + size / 2, y, size / 2);
        divide(x, y + size / 2, size / 2);
        divide(x + size / 2, y + size / 2, size / 2);
    }
}

int main()
{
    int i, j;

    // 종이 크기
    scanf("%d", &n);

    // 종이 색
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            scanf("%d", &paper[i][j]);
        }
    }

    divide(0, 0, n);

    printf("%d\n%d\n", white, blue);

    return 0;
}

 

2630

---

• 다이나믹 프로그래밍 → 가장 긴 공통 부분 찾기

// 9251.c

#include <stdio.h>
#include <string.h>

// 길이 저장(테이블)
int dp[1001][1001];

int main()
{
    char a[1001], b[1001];
    int i, j;

    // 문자열 입력
    scanf("%s", a + 1);
    scanf("%s", b + 1);

    // 문자열 길이
    int len_a = strlen(a + 1);
    int len_b = strlen(b + 1);

    // 테이블
    for (i = 1; i <= len_a; i++)
    {
        for (j = 1; j <= len_b; j++)
        {
            // 두 문자가 같으면
            if (a[i] == b[j])
            {
                // 1 더하기
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            // 다르면
            else
            {
                // 옆의 값 중 큰 것으로
                dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    printf("%d\n", dp[len_a][len_b]);

    return 0;
}