이차원 배열이 있고
가운데요소와 상하좌우대각선합을 비교해서 차가 1일때 임의로 제가 0,1로 집어넣은후
쭉 재귀로 돌았습니다
그랬을때 가운데요소와 전체 합이 다른경우가 발생하면 저 임의로 넣은 0,1 위치로 가서
1,0으로 바꿔야할것 같은데
이걸 어떻게해야될지 모르겠어요ㅠㅠㅠㅠㅠ
저는 이 문제가 왜 백트래킹이 필요한지 이해가 안 되는군요.
지뢰의 위치를 찾는 게 아니라 지뢰의 갯수를 세는 게 문제라면, 답이 너무 명백하지 않습니까?
12110
##*## 에 숨겨진 지뢰가 총 몇 개냐고요?
(121)(10)
(##*)(##) 이렇게 쪼개 놓고 보면, 첫째 블록엔 지뢰가 두 개, 둘째 블럭엔 지뢰가 없죠.
그러니까 2+0=2개.
(111)(22)
(###)(#*) 1 + 2 = 3개
(233)(21)
(###)(##) 3 + 1 = 4개
조금만 머리를 쓰면 N이 어떤 수이든 첫 줄에 주어진 지뢰 분포에서 적당한 방법으로 선택하기만 하면
서로 겹치지 않는 구간으로 나누어 위와 같이 간단히 전체 지뢰 수를 구할 수 있게 된다는 걸 보일 수 있습니다.
구체적인 과정은 직접 해보세요. 힌트를 드리자면 N=3k-2, 3k-1, 3k인 경우에 대해 나누어 증명하면 됩니다.
https://www.acmicpc.net
https://www.acmicpc.net/problem/9082
이걸 2차원 배열로 나타냈을때 어떻게 계산을 해야할지 모르겠어요
저는 이 문제가 왜 백트래킹이 필요한지 이해가 안
저는 이 문제가 왜 백트래킹이 필요한지 이해가 안 되는군요.
지뢰의 위치를 찾는 게 아니라 지뢰의 갯수를 세는 게 문제라면, 답이 너무 명백하지 않습니까?
12110
##*## 에 숨겨진 지뢰가 총 몇 개냐고요?
(121)(10)
(##*)(##) 이렇게 쪼개 놓고 보면, 첫째 블록엔 지뢰가 두 개, 둘째 블럭엔 지뢰가 없죠.
그러니까 2+0=2개.
(111)(22)
(###)(#*) 1 + 2 = 3개
(233)(21)
(###)(##) 3 + 1 = 4개
조금만 머리를 쓰면 N이 어떤 수이든 첫 줄에 주어진 지뢰 분포에서 적당한 방법으로 선택하기만 하면
서로 겹치지 않는 구간으로 나누어 위와 같이 간단히 전체 지뢰 수를 구할 수 있게 된다는 걸 보일 수 있습니다.
구체적인 과정은 직접 해보세요. 힌트를 드리자면 N=3k-2, 3k-1, 3k인 경우에 대해 나누어 증명하면 됩니다.
댓글 달기