글 읽기 - 색종이 붙이기 35%에서 못 올라갑니다 ㅠㅠ

soma012 3년 전 1

f는 색종이를 채우는 함수

chk는 색종이를 채울 수 있는지 검사하는 함수로 만들었습니다.

모든 경우를 탐색해보는 방식으로 구현했는데 틀렸습니다가 뜨네요 ㅜ

도움 부탁드립니다 ..

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int p[10][10], ans=101;
bool ispos=false; // 종이를 덮을 수 있으면 true
void f(int r, int c, int d, int t) { // r,c부터 가로세로 범위 d까지 t로 채우는 함수
    for(int R=r; R<r+d; R++)
        for(int C=c; C<c+d; C++) p[R][C]=t;
}
bool chk(int r, int c, int d) { // r, c부터 가로세로 범위 d 내에 0이 있으면 false
    for(int R=r; R<r+d; R++)
        for(int C=c; C<c+d; C++)
            if(p[R][C] ==0) return false;
    return true;
}
void go(int pap[5], int x, int cnt) {
    if(x==100) {
        bool flag = true;
        for(int i=0; i<10; i++)
            for(int j=0; j<10; j++)
                if(p[i][j]) {flag=false; break;} // 덮지 못한 부분이 있는지 체크
        if(flag) { // 모두 덮었다면
            ispos=true;
            ans=min(ans, cnt);
        }
        return;
    }
    int r=x/10, c=x%10;
    if(p[r][c]==0) go(pap, x+1, cnt);
    else {
        for(int rn=1; rn<=5; rn++) {
            if(!chk(r,c,rn) || pap[rn-1]==0) continue;
            f(r,c,rn,0);
            pap[rn-1]--;

            go(pap, x+1, cnt+1);

            pap[rn-1]++;
            f(r,c,rn,1);
        }
    }
}
int main() {
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++) cin>>p[i][j];
    int PAP[5]={5,5,5,5,5}; // 색종이 갯수를 저장하는 배열
    go(PAP, 0, 0);
    
    if(ispos) cout << ans;
    else cout << -1;
}

sunjoo9912 3년 전 2

저도 35퍼에서 틀렸었는데 종이 덮을 수 있는지 없는지 체크하는 함수에서 좌표가 10*10 범위 밖으로 나가면 false 반환하도록 처리 하니까 통과됐어요

chk 함수에 좌표 범위 확인하는 코드 한번 넣어보세요..!

soma012 2년 전 0

아.. 왜 그 생각을 못했을까요 ㅠㅋㅋ 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

색종이 붙이기 35%에서 못 올라갑니다 ㅠㅠ

soma012 3년 전 1

sunjoo9912 3년 전 2

soma012 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말