SLENDER ANKLES's 개발블로그

백트래킹 문제에 대해서 조금씩 감을 잡아가는 느낌이다.

이 문제는 완전 탐색을 하는 도중 첫 번째 답이 나오면 종료하는 것이 포인트다. 

나의 백트래킹 가지치기는 1부터 3으로 한 칸씩 늘려나가면서 만들어 가므로 

가장 먼저 나오는 첫 번째 답이 최소값이다. 그렇다면 더 이상 트래킹을 그만둬도 답을 도출해낼 수 있다. 

백트래킹에 대한 문제는 어느 정도 해소가 되었는데,

좋은 수열을 판별하는 방법이 의외로 까다로웠다.

처음에는 좋은 수를 판별하는 방법은 너무 복잡하고 까다롭고 분명 시간 소비를 많이 할 것 같아 

규칙을 찾아야 된다고 생각했는데, 그 것이 아니었다. 

좀 더 연구해보니까 분명 좋은 수열을 판별하는 것은 

인덱스 장난을 치는 부분이 조금 복잡하지만 절대 시간이 오래 걸리지는 않다는 것을 알았다. 

예를 들어 123123 이라는 수가 있으면

맨 끝의 인덱스부터 시작해서 length를 1부터 시작해서

length : 1

2-3 비교

-----------------------

length : 2

3 - 1

2 - 3

비교

-----------------------

length : 3

3 - 3 

2 - 2

1 - 1

비교 ===>(이 것은 나쁜 수열로 판별남)

-----------------------

이런식으로 판별했다. 

(현재의 점)을 기준으로 현재 점과 (현재의 점 - length)을 비교하는 과정을 통해

판별하는 것이다. 이 경우는 길이가 80이어도 40번만 수행 횟수는 정말 얼마 되지 않는다. 40번정도?

수를 완전탐색하면서 좋은 수열인지 판별하고 답이 나오면 최소값이므로 바로 종료하면 되는 문제였다.

<소스코드>

직관적으로 이 것은 점들의 평균 값이겠다 했는데, 평균 값이 아니라 중앙값을 선택하는 문제였다. 

x, y를 각각 정렬 한 후에 그 배열의 중간 값이 최소거리를 갖게하는 점이다. 

각 점들에게 이 점까지의 거리를 구하면 답이 나온다. 

정확하게 증명하기는 어렵지만 이러한 문제가 나오면 평균값이 안되면 중앙값으로 시도해보는 것도 한 패턴일 것 같다.

n의 범위는 10000, m의 범위는 100000이었는데,

계속 x,y의 범위를 10000까지만으로 해서 ... 계속 틀렸다. 

문제를 잘 읽어봐야 하겠다.

완전탐색으로 구현하다가 낭패 본 문제

11122 ####*

위 쪽의 입력은 자신의 인덱스의 좌, 자신, 우의 지뢰의 개수를 가르쳐준다.

입력의 윗 부분만 보면 된다. 

첫 번째 입력이 2인 경우

result[0] = 1, result[1] = 1 로 세팅 한 후에 

result[idx - 1] + result[idx] + x == mine[idx] 인 x를 찾아서 result[idx + 1]에 대입시켜주며 재귀 함수를 수행하면 된다.

첫 번재 입력이 0인 경우

result[0] = 0, result[1] = 0 로 세팅 한 후에 

result[idx - 1] + result[idx] + x == mine[idx] 인 x를 찾아서 result[idx + 1]에 대입시켜주며 재귀 함수를 수행하면 된다.

첫 번째 입력이 1인 경우

result[0] = 1, result[1] = 0 으로 세팅 한 후에

위의 재귀 동작을 수행 시켜서 마지막 인덱스의 답이 맞으면 넘어가고

틀리면

result[0] = 0, result[1] = 1으로 세팅 한 후에 

위의 재귀 동작을 수행 시키면 된다.

이렇게 하면 무조건 답이 나온다. 

범위가 100까지 이므로

완전탐색의 최악의 경우 2^100이므로 절대 완전탐색을 하면 안되는 문제였다. 

분명 규칙을 찾아야 하는 문제였는데, 

백트래킹으로 풀려다가 계속 안 풀린 문제였다. 

계산해봐서 절대 시간안에 풀수 없는 문제이면 완전탐색 시도를 하면 안되고 무조건 규칙을 찾아야 한다는 것을 깨달았다.