[백준 27921번] 동전 퍼즐 (C++)

문제링크 : https://www.acmicpc.net/problem/27921

27921번: 동전 퍼즐

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

char c1[11][11];
char c2[31][31];

int H1, W1, H2, W2;
int cnt = 0;
int maxV = 0;

void func(int idx_H, int idx_W) //우로 이동 탐색
{
    cnt = 0;
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            if(c1[i][j] == c2[i+idx_H][j+idx_W] && c2[i+idx_H][j+idx_W] == 'O') cnt++;  //제일 많이 겹치는 'O' 개수 카운트
        }
    }
    maxV = max(maxV, cnt);
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> H1 >> W1;

    for(int i=0; i<H1; i++)
    {
        for(int j=0; j<W1; j++)
        {
            cin >> c1[i][j];
        }
    }

    cin >> H2 >> W2;

    int total = 0;
    for(int i=0; i<H2; i++)
    {
        for(int j=0; j<W2; j++)
        {
            cin >> c2[i+10][j+10];
            if(c2[i+10][j+10] == 'O') total++; //총 개수 카운트
        }
    }

    for(int i=0; i<=30-H1; i++)
    {
        for(int j=0; j<=30-W1; j++)
        {
            func(i, j); //완전탐색
        }
    }

    cout << total - maxV;
    
    return 0;
}

기본적인 방식은 완전 탐색으로 처음에 우측으로 쭉 탐색했다가, 아래로 한칸 이동하고 다시 우측으로 쭉 탐색하는 걸

반복하는 것이다.

 

처음에 이것만 구현하고 인덱스 범위 설정을 잘못하여 한참을 헤맸다.

문제는 c1과 c2과 완전히 겹치는 부분만이 아니라, 동서남북 방향으로 살짝만 겹치는 부분도 검사를 해야 한다.

그래서 원래 범위는 10이지만, 좌로 10 / 중앙 10 / 우로 10 해서 범위를 30으로 늘려서 탐색해야 한다.

우리가 찾는건 중앙에 해당하므로 처음 입력은 c2[i+10][j+10] 이렇게 10을 더해줘서 중앙에 위치하도록 한다.

 

그리고 탐색할때 c1의 크기가 있으므로 가로세로에 대해서 총 크기인 30에서 c1의 가로세로 크기인 H1, W1 만큼 빼준만큼만 탐색해도 된다.

해당 사각형이 원하는 위치까지 딱 포함되기 때문이다.

참고용 그림