백준, C++) 1018, 1436, 2839

1018

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

슬라이딩 윈도우의 개념을 몰랐다가 처음 알게 되어 이것 저것 찾아가면서 풀이

추가로 wb와 bw의 관계가 opposite관계 인걸 이용해서 마지막 결과 값을 바꿔주면 bw인걸 다시 할 필요 없이 처리 가능

슬라이딩 윈도우 관련 설명

https://www.youtube.com/watch?v=ot5mnp_hTqo

void p1018()

{

    // 8<= M, N <=50

    string WB[8] = {

        "WBWBWBWB",

        "BWBWBWBW",

        "WBWBWBWB",

        "BWBWBWBW",

        "WBWBWBWB",

        "BWBWBWBW",

        "WBWBWBWB",

        "BWBWBWBW"};

    string BW[8] = {

        "BWBWBWBW",

        "WBWBWBWB",

        "BWBWBWBW",

        "WBWBWBWB",

        "BWBWBWBW",

        "WBWBWBWB",

        "BWBWBWBW",

        "WBWBWBWB"};

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int N, M;

    cin >> N >> M;

    vector<string> board(N);

    for (int i = 0; i < N; ++i)

        cin >> board[i];

    int answer = 64; // 8x8 최대 칠하기 수, 64로 설정하지 않고 그냥 큰 값으로 설정해도 됨.

    // 첫 이중 for문

    // -슬라이딩 윈도우의 범위 설정

    // - +8인 이유: 0 - 10까지 라면 (0~ 8), (1~9), (2~10) 이런 식

    // 슬라이딩 윈도우: 8x8 창의 좌상단 (i, j)을 보드 위에서 이동

    for (int i = 0; i + 8 <= N; ++i)

    {

        for (int j = 0; j + 8 <= M; ++j)

        {

            // (i,j)에서 시작하는 8x8 구간을 'WB' 템플릿과 비교

            // W시작일 때로 계산, cnt는 윈도우 범위가 바뀔때마다 초기화

            int cntW = 0;

            for (int r = 0; r < 8; ++r)

            {

                for (int c = 0; c < 8; ++c)

                {

                    if (board[i + r][j + c] != WB[r][c]) // 윈도우 범위 내의 문자가 WB와 다르다면?

                        ++cntW;

                }

            }

            // 'B' 시작(=BW)은 W 시작과 정확히 반대임.

            // 현재까지의 가장 작은 값을 answer에 저장

            int repaint = min(cntW, 64 - cntW); // wb와 bw 고려

            answer = min(answer, repaint);

        }

    }

    cout << answer << '\n';

}

 

1436

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

void p1436()

{

    // 1<= N <= 10,000

    int N;

    cin >> N;

    int temp = 665;

    int cnt = 0;

    while (cnt < N)

    {

        ++temp;

        // "666"을 적어도 한 번 포함한다 (어디에 있든)

        // find를 사용했을 때, 못찾으면 npos를 반환

        // 즉, 찾았으면 npos를 반환하지 않고 인덱스 값이든 뭐든 반환

        // 반환한게 npos가 아닌 666의 index라면, 즉 찾았다면

        if (to_string(temp).find("666") != string::npos)

        {

            ++cnt; // cnt값을 1개 더하고 cnt에 저장

        }

    }

    cout << temp << '\n';

}

 

2839

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

 

이전에는 1,2,4,7과 같은 1의 자리는 예외 처리를 두고, %5 ==0, %8==0 등 나머지에 대해서 풀려했는데 그럴 필요가 없었음.

한번에 처리가 가능하도록 수정

void p2839()

{

    // 문제

    // 정확히 N킬로그램 배달 -> 3<= N <= 50,000

    // 각 3키로, 5키로 만큼의 설탕봉지 있음.

    // 최대한 적은 봉지

    // 정확히 몇 봉지?

    // for문은 범위 지정이므로, 그 범위를 유연하게 설정합시다.

    int N;

    cin >> N;  

    for (int five = N / 5; five >= 0; --five) {

        int rem = N - 5 * five;

        if (rem % 3 == 0) {

            int three = rem / 3;

            cout << (five + three);

            return;

        }

    }

    cout << -1;

}