BOJ 1018번 체스판 다시 칠하기 문제 자바(java) 풀이
문제 정리
- MxN 크기의 보드가 있다.
- 흰색과 검은색의 정사각형으로 이루어져 있다. 8x8 체스판을 만드려고 한다.
- 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져야 한다. -> 체스판을 색칠하는 경우는 2가지
- MxN 크기의 보드에서 8x8 크기의 체스판으로 잘라서 색을 다시 칠하려 한다.
- 다시 칠해야 하는 정사각형의 최소 개수를 구하여라
문제 접근
완전 탐색만 할 줄 안다면 풀 수 있는 문제입니다. 간단하게 생각해야 합니다.
4중 for문으로 답을 구해낼 수 있습니다.
- 8x8로 자를 수 있는 가능한 경우 모두 잘라본다
- 자를 때 마다 체스판과 다른 문자 갯수를 찾아서 저장하고 최소 값과 비교하여 작다면 업데이트 한다.
문제 풀이
- 열의 index를 먼저 정한다. (j)
- 행의 iddex를 정한다.(t)
- 열과 행의 index가 정해졌으므로 t부터 8개의 행을 비교한다. (i (t부터 8칸 확인))
- 행이 체스판과 똑같은 경우는 열의 문자를 각각 탐색하지 않는다.
만약 같지 않다면 체스판의 행들의 문자들을 각각 비교해서 다른 것의 개수를 더해나간다. (k) 이때 j부터 8칸만 확인한다.
- 최소값을 갱신하고 sum 변수들을 초기화 시켜준다.
- 두 체스판의 최소값인 min1과 min2 중 더 작은 값을 출력한다.
백준 체스판 다시 칠하기 자바 코드