[백준] 1518번

또 슬금 들어와서 문제 하나 끄적이고 가기

코딩테스트가 코앞인데 졸업 작품도 준비중이라 정신이 없다.🥺

그치만 또 바쁜게 좋은 ESTJ는 그냥 이 상황을 즐기기로...

오늘은 간단하게 1518번 풀이!

 

문제출처: https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

처음에는 반복문마다 deepcopy를 이용해 8행 8열씩 배열을 만들고,

deepcopy된 배열 내에서 완전탐색으로 상하좌우와 다른 알파벳인지 확인하는 방식으로 해결하려고 했다.

그런데 이렇게 하면 같은 색칠이 된 부분을 기점으로 자꾸 새롭게 칠해서 중복되는(?) 현상이 발생한다.

위의 문제뿐만 아니라 이중 반복문 내에서 계속해서 deepcopy가 이루어지므로 효율성도 떨어진다.

실컷 코드를 작성하고 결과를 출력해보면서 copy까지 할 필요가 없겠구나 했다. 어렵게 돌아갔당..

 

3~6번째 줄은 위에서 작성한 것처럼 처음에 생각했던 방식이다.

체스판의 특징을 잘 생각해보면 그래프 문제가 아니라 수학문제로 풀이가 가능하다.

체스판의 특징은 '대각선이 같은 색'이다. 즉, 행과 열의 인덱스를 합한 값이 짝수/혹은 홀수이면 각각 같은 색이다.

체스판의 맨 첫번째 칸인 0,0 역시 2로 나누었을 때 나머지가 0이므로 짝수라고 두면, 첫 번째 칸을 'W' 또는 'B'로 두는 두 가지 경우가 된다.

 

k,l 반복문 내에서 첫 번째 칸이 'W', 홀수일 때 'B'라고 가정하고 조건에 맞지 않으면 cnt 값을 1씩 증가시킨다.

이때 전체 판의 정보는 계속해서 사용해야하므로 보존을 위해 색칠 값을 덮어씌우지 않는다.

앞서 나는 첫 번째 칸이 'W'일 때를 가정했지만 첫 번째 칸이 'B'일 때 칠해야 하는 값이 더 작다면?

체스판은 8x8 = 64개의 칸을 가지고 있다. 따라서 첫째 칸이 'W'일 때 칠해야 하는 값을 64에서 빼주면 그 값이 나온다.

결국 선택한 8x8 내에서 값은 min(cnt, 64-cnt) 가 된다.

 

i,j 반복문 내에서 8x8을 선택하는 모든 경우의 수가 적용된다.

j 반복문이 끝날 때마다 ans = min(ans, cnt, 64-cnt)를 이용하여 셋 중 가장 작은 값을 적용한다.

(ans의 초기값을 64로 둔 경우는 체스판을 모두 다시 칠해야하는 최악의 경우를 가정)

 

 

지금 마법사 상어와 비바라기 풀고있는데...

이 거칠고 험난한 세상 마법사 상어 앞에서 내가 헤쳐갈수잇을까

아무튼 시간이 된다면 그것도 업로드 해야겠다

안뇽!