[백준(BOJ)/C++] 18111번: 마인크래프트 - 코딩밥상

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

18111번: 마인크래프트

 

• 접근 방법, 논리 흐름(알고리즘)

 전에 풀었던 브루트포스 문제들과 다른점은 순열이나 조합을 사용하지 않고 말 그대로 완전탐색을 통해 모든 경우를 확인해 보았다.

2차원 배열로 땅을 입력 받고 처음에는 칸 하나하나를 기준점으로 두고 완전탐색을 했는데 시간초과가 나서, 문제를 자세히 읽어보니 높이의 최대값이 256인 것을 알고 높이(0~256)를 기준으로 잡고 탐색하였다.

여기서 까다로웠던 점은 여분의 블록 즉 메꿀 수 있는 땅의 높이도 신경써서 따로 조건문으로 뺴주는 것이었다. 또 땅을 파면 블록을 파밍하여 여분의 블록이 늘어난다.

따라서 기준점과 나머지 모든 블록들을 비교하면서 여분의 블록과 메꿀 땅의 높이를 매순간 비교하여 가능 여부를 판단하여 답을 제출하니 틀렸다.

천천히 삽질해가며 깨달은 점은 어차피 파밍을 하면 여분의 블록을 얻을 수 있기 때문에 중간에 메꿀 수 없는 땅도 나중에는 메꿀 수 있는 경우가 생기는것이다.  이를 해결하기 위해 팔 땅과 메꿀 땅을 저장하여 탐색을 모두 마친 후 마지막에 가능 여부를 조사하는 것이다.

 

 

• 구현