BFS :: 백준 :: 배열에서 이동 :: 1981

배열에서 이동

https://www.acmicpc.net/problem/1981

탐색이다!! 너비 우선 탐색을 해야 할 것 같은 느낌이 들긴 하는데...

DP를 같이 써야 하나?? 

고민하다 알고리즘 분류를 보니 BFS + 이분탐색 이다.

이분탐색이라니.. 어느 부분에서?? 흠흠.....

오래 걸리기도 하고 많이 틀리기도 한 문제

[문제 풀이]

1. 숫자들을 입력받는다. 입력받을 때 max값과 min값을 저장해놓는다.

2. (int) diff = max - min을 구한다.  

     => 우리는 max - min의 최솟값을 찾아야 한다.

     => 그리고, 우리가 구하고자 하는 답의 범위는 0 <= ans <= diff 이다!!

3. 이분탐색과 BFS를 병행해가며 답을 찾는다.

     => 배열의 크기는 최대 100 X 100 이고, 숫자의 최대, 최소는 각각 0, 200 이므로 전체 연산은 150000번정도?? 제한시간 안에 충분히 끝낼 수 있다. 

풀이를 보면 굉장히 간단해 보이지만, 아이디어를 떠올리고, 답을 맞추는데 굉장히 많은 시간이 걸렸다.. ㅠ__ㅠ