문제
정올이는 암벽등반을 시도하려고 한다.
암벽등반을 하기 위해서는 체력을 길러두어야 한다.
등산 장소는 각 장소의 돌출 정도가 표시되며 많이 튀어나와 있을수록 그 값이 크다.
각 지점의 돌출 정도는 0~1,000,000 중 하나의 값을 가진다.
체력은 H로 표현되며, 체력이 H라면 현재 위치에서 ±H이하의 상, 하, 좌, 우 장소로 이동할 수 있다.
따라서 체력이 높을수록 어려운 암벽등반에서 완주할 가능성이 높아진다.
정올이가 이번에 참가할 암벽등반 대회의 등산로의 정보가 지도로 주어진다.
지도는 N*N으로 구성된 정사각형이다.
암벽등반의 성공 여부는 주어진 지도의 3/4 이상의 장소를 지나가야 성공으로 판정한다.
정올이는 임의의 장소에서 출발할 수 있고, 끝나는 장소도 임의의 장소에서 끝낼수 있다.
다만, 전체 등반 장소의 3/4이상을 이동해야 한다. 정올이가 주어진 지도의
암벽등반을 무사히 완주하기 위해서 필요한 최소 H를 구하는 프로그램을 작성하시오.
단, 3/4가 실수일 경우에는 소수점 이하를 버린 값만큼만 등반하면 성공으로 본다.
만약 N이 9라면 모두 81개의 등반 장소가 있고,
이중 3/4는 60.75이므로 60개의 등반 장소를 등반했을 경우 성공한 것으로 본다.
입력
첫 번째 줄에는 등산 장소의 크기 N이 주어진다.
다음 줄부터 N줄에 걸쳐서 N개의 영역별 높이가 공백으로 구분되어 주어진다.
N의 값은 500이하의 자연수이고,
각지점의 돌출 정도는 0부터 1,000,000까지의값 중 하나의 값을 가진다.
출력
등반을 성공적으로 마칠 수 있는 최소 H값을 출력한다.
예제
5
9 9 9 3 3
0 0 0 0 3
0 9 9 3 3
0 0 0 3 3
9 0 0 9 3
3
출처
문제해결을 위한 창의적 알고리즘 (고급)
로그인해야 코드를 작성할 수 있어요.