= 내가 접근한 방법 ( 틀림 ) =
문제 의도 자체를 잘못 파악했다.
내가 이해한 내용은 8x8체스판에서 B와 W의 개수를 구한 후, 제일 최소로 각자 32개씩 나올 수 있는 방법을 찾았다.
그래서 틀렸다
이 문제는 8x8 배열에서 W,B가 교차하면서 완벽하게 체스판을 만들어야 할 때 필요한 W,B의 갯수지
8x8체스판에서 B와 W의 개수를 구한 후 , 완전하게 새로 칠한다는 문제가 아니였다.
이 방법을 엄청 고민하면서 풀었는데 틀렸고, 더이상 해결 방법을 찾지 못해 구글링을했다.
= 다른 사람 풀이 =
정말 간단하게 풀 수 있었다.
0. 맨 처음 배열을 생성해서 1차원 배열로 BBBBBBBB, WWWWWWWW 이런식으로 row값에 맞게 저장한다.
1. 체스판을 자른다.
8x8의 모든 경우의 수를 생각하면 된다.
내가 input을 10x10으로 입력했다면
8x8로 쪼개기 위해서는 어떻게 해야 될까?
9가지의 경우의 수가 있다.
이런식으로 총 9가지의 경우가 나온다.
10x10으로 입력을 했으니까,
i = 0~2 즉 높이는 0~2까지, j = 0~2 즉 가로도 0~2까지 범위를 확장할 수 있고 이렇게 자를 수 있다는 뜻이다.
2. 현 체스판의 최소 비용 구하기
getSolution 함수를 보자
맨 왼쪽 위칸이 white인 체스판을 만드는 경우만 생각하면 된다.
강의를 들었을 때도, 이 부분이 많이 헷갈렸는데
나는 맨 위 맨 왼쪽이 White인 체스판을 만들 것이고 그것을 기준으로 계산을 할 것이다 라는 것만 생각하면 이해할 수 있는 문제였다.
borad를 하나하나씩 original이랑 비교하는 과정이다.10x10을 기준으로 startRow와 startCol은 0~2까지 들어올 수 있고, originalBoard는 첫번째 두번째 첫번째 두번째 계속white체스판을 만들 수 있는지 체크하는 과정이기 때문에 row % 2를 해줘서 0~1만 반복할 수 있게 하는 것임.
이런식으로 이 문제를 해석하고 쉽게 풀 수 있는게 너무 부러웠다.
3. 전체 최적의 값과 비교하여 갱신하기
왜 black체스판과 white체스판 두 개를 다 구하지 않았는 지 여기서 알 수 있다.
2x2체스판이라고 가정을 해보자
B W 체스판이 존재하면 black체스판으로 만드려면 count가 몇 인가? => 1개다. 1개만 바꾸면 된다
W W
white체스판으로 만드려면 count가 몇 인가? => 3개다.
W B 이 모양으로 바꾸려면 3개를 바꿔야 한다.
B W
즉, 2x2 배열은 4로 나타낼 수 있고 white값 or black값만 구하면 나머지 값을 구할 수 있다.
4 - white => 4 - 3 = "1" 따라서 하나의 값으로 나머지 하나를 구할 수 있다!!
그렇기 때문에 getSolution 함수 return 값이 이거인 것임.
최소값을 찾기 위해서
getSolution 함수를 들어갈 때 마다, 최솟값을 뽑아내고
그 뽑아낸 최솟값을 계속 solutin이라는 int 변수에 갱신을 해주면 최종적으로 최솟값을 구할 수 있다.
최근에 발견한 영상인데 다른 풀이들도 엄청 섬세하고 개념들도 잘 짚어주시기 때문에 보는 것을 추천한다.
이 문제는 이 링크로 공부했다.
https://www.youtube.com/watch?v=QQUb4b6iWSw
'백준 오답노트 > 브루트포스' 카테고리의 다른 글
| 백준 - 브루트포스 1436번 영화감독 숌 / 문제를 이해 못 함. (0) | 2022.12.12 |
|---|---|
| 백준 - 브루트포스 2231번 분해합 / 백준 질문글로 해결 (0) | 2022.12.08 |
