[BOJ] 백준 18111 마인크래프트 (JAVA)

실버2 하드코어버전..

📑 문제

백준 18111번 마인크래프트

---

🌱 아이디어

이 문제는 한 블록당 숫자를 기준으로 푸는 것이 아닌 평탄화 기준이 될 땅 높이를 기준으로 탐색한다!

 

처음엔 문제에서 말한 조건 1,2번을 DFS로 풀어서 한 블록을 기준으로 평탄화 작업을 하려고 했는데...

안된다는 것을 빨리 깨달았다... 이 문제는 "땅의 높이는 256블럭 보다 작거나 같은 자연수 또는 0 이다"  라는 말을 이용해서 풀어야 한다

 

예를 들어 결국 평탄화 작업을 통해 나오는 땅의 높이는 0 ~ 256까지의 경우가 있다.

즉 우리는 0~256까지 경우의 평탄화 기준 땅높이를 토대로 조건 1,2번과 인벤토리를 통해 평탄화할 수 있는지

판단하고 평탄화 가능 하다면 최소 시간을 구해야 한다!

 

주석을 통해 코드마다 설명을 남겨놨으니 천천히 보면 이해하는데 어렵지 않을 것이다.

---

🌱 코드 및 풀이

이 문제를 풀면서 0 ~ 256까지 전체탐색 하는 것보다 배열에 입력된 값 중 min, max을 구해서 범위 내에서 탐색

해보는 것 도 실험해 봤으나 이 문제에서는 큰 효과를 보지는 못했다..

 

ground = ground - start; 부분에서 if 문을 통해 음수인지 양수인지를 판단해 놨는데

 

평탄화를 높이 10으로 할 때 ground - 10이 양수라면  블록을 제거해야 하고 음수라면 블록을 설치해야 한다

모든 작업이 끝난 후 인벤토리 안에  블록이 0개 이하라면 높이 10으로 평탄화를 시킬 수 없는 경우가 된다! 

 

 

---

🌱 느낀 점

문제를 풀고 나면 다른 사람들 풀이도 참고하는데 대부분 내가 떠올린 아이디로 문제를 풀었던 것 같다 ㅎㅎ

정공법으로 푼 것 같아서 뿌듯했고, 660ms가 나왔는데 단축시킬 수 있는 방법을 생각해 봐야겠다!