Created
October 29, 2020 13:03
-
-
Save overnew/fd3d21962d9ff3148904d97c1e47286a to your computer and use it in GitHub Desktop.
백준_17136_색종이 붙이기_C++코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
using namespace std; | |
const int boardSize = 10; | |
int board[10][10]; | |
int minUsedPaperNum=25; //최대 사용개수는 25 | |
int remainedColoredPaper[6] = {0,5,5,5,5,5}; | |
bool CheckPosFill(int paperSize, int r, int c){ | |
for(int i=r; i<r+paperSize ; ++i) | |
for(int j=c; j<c+paperSize ; ++j) | |
if(board[i][j] != 1) | |
return false; | |
return true; | |
} | |
void FillBlocks(int paperSize, int r, int c,int& remainedBlocksNum, bool fill){ | |
if(fill){ | |
for(int i=r; i<r+paperSize ; ++i) | |
for(int j=c; j<c+paperSize ; ++j) | |
board[i][j] = 0; | |
remainedBlocksNum -= paperSize*paperSize; | |
} | |
else{ | |
for(int i=r; i<r+paperSize ; ++i) | |
for(int j=c; j<c+paperSize ; ++j) | |
board[i][j] = 1; | |
remainedBlocksNum += paperSize*paperSize; | |
} | |
return; | |
} | |
void FillColoredPaperDfs(int row, int col,int remainedBlocksNum,int usedPaperNum){ | |
if(col >= boardSize){ | |
FillColoredPaperDfs(row+1, 0,remainedBlocksNum,usedPaperNum); | |
return ; | |
} | |
if(row>= boardSize){ | |
minUsedPaperNum = minUsedPaperNum < usedPaperNum ? minUsedPaperNum : usedPaperNum; | |
return; | |
} | |
if(board[row][col] ==0){ | |
FillColoredPaperDfs(row,col+1 ,remainedBlocksNum,usedPaperNum); | |
return; | |
} | |
if(usedPaperNum >= minUsedPaperNum) | |
return; | |
if(remainedBlocksNum ==0){ | |
minUsedPaperNum = minUsedPaperNum < usedPaperNum ? minUsedPaperNum : usedPaperNum; | |
return; | |
} | |
for(int paperSize=5; paperSize>0 ; --paperSize) | |
if(remainedColoredPaper[paperSize] >0 && remainedBlocksNum >= paperSize*paperSize) | |
if(row+paperSize<=boardSize && col+paperSize<=boardSize) | |
if(CheckPosFill(paperSize, row, col)){ | |
--remainedColoredPaper[paperSize]; | |
FillBlocks(paperSize,row,col,remainedBlocksNum,true); | |
FillColoredPaperDfs(row,col+paperSize,remainedBlocksNum,usedPaperNum +1); | |
FillBlocks(paperSize,row,col,remainedBlocksNum,false); | |
++remainedColoredPaper[paperSize]; | |
} | |
return; | |
} | |
int main() { | |
int remainedBlocks=0; | |
ios_base::sync_with_stdio(0); cin.tie(0); | |
for(int i=0; i<boardSize ; ++i) | |
for(int j=0; j<boardSize ; ++j){ | |
cin>>board[i][j]; | |
if(board[i][j] == 1) | |
++remainedBlocks; | |
} | |
FillColoredPaperDfs(0,0,remainedBlocks,0); | |
if(minUsedPaperNum == 25) | |
cout<<-1<<'\n'; | |
else | |
cout<<minUsedPaperNum<<'\n'; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment