반응형

프로그래밍 알고리즘 81

[정올 2543] 타일 채우기

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1804&sca=99&sfl=wr_hit&stx=2543 JUNGOL www.jungol.co.kr #include /* 분할 정복 문제 1. 처음에 N * N 행렬이 있고, 채울 수 없는 H이 하나 있다. 2. 행렬을 4등분하여 H가 없는 사분면 중간에 블럭을 추가한다. 3. 2번이 끝나면, 각 사분면에 채울 수 없는 1개짜리 블럭이 각각 1개씩 있게 된다. (원래 H있는 사분면 1개 + 블럭 추가한게 1개씩 들어간 사분면 3개) 즉, 원래 문제와 똑같은데 크기만 4분의 1로 작아진 4개짜리 문제가 생기는 것이다. 4. 3번에서 생긴 4개의 4분면을 가지고 2번~3번을 반복한다. 이렇게 반복하면 2..

반응형