새소식

알고리즘 문제풀이/BOJ

[BOJ] 백준 1018번 체스판 다시 칠하기 자바(java) 풀이 (완전탐색)

  • -

BOJ 1018번 체스판 다시 칠하기 문제 자바(java) 풀이

문제 정리

  1. MxN 크기의 보드가 있다.
  2. 흰색과 검은색의 정사각형으로 이루어져 있다. 8x8 체스판을 만드려고 한다.
  3. 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져야 한다. -> 체스판을 색칠하는 경우는 2가지
  4. MxN 크기의 보드에서 8x8 크기의 체스판으로 잘라서 색을 다시 칠하려 한다.
  • 다시 칠해야 하는 정사각형의 최소 개수를 구하여라


문제 접근

완전 탐색만 할 줄 안다면 풀 수 있는 문제입니다. 간단하게 생각해야 합니다.
4중 for문으로 답을 구해낼 수 있습니다.

  1. 8x8로 자를 수 있는 가능한 경우 모두 잘라본다
  2. 자를 때 마다 체스판과 다른 문자 갯수를 찾아서 저장하고 최소 값과 비교하여 작다면 업데이트 한다.


문제 풀이

  1. 열의 index를 먼저 정한다. (j)
  2. 행의 iddex를 정한다.(t)
  3. 열과 행의 index가 정해졌으므로 t부터 8개의 행을 비교한다. (i (t부터 8칸 확인))
  4. 행이 체스판과 똑같은 경우는 열의 문자를 각각 탐색하지 않는다.
    만약 같지 않다면 체스판의 행들의 문자들을 각각 비교해서 다른 것의 개수를 더해나간다. (k) 이때 j부터 8칸만 확인한다.
  5. 최소값을 갱신하고 sum 변수들을 초기화 시켜준다.
  6. 두 체스판의 최소값인 min1과 min2 중 더 작은 값을 출력한다.

백준 체스판 다시 칠하기 자바 코드

Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.