[ Java ] 18111번 - 마인크래프트
< 문제 정보 >
[ 문제 ]
마인크래프트라는 게임 내에서 집을 짓기 위한 부지를 평평하게 하는 작업을 할 것이다.
부지를 최저 시간과 최고 높이로 하기 위해서는 어떤 높이로 설정해야 하는가를 출력하는 문제[ 예시 ]
입력 :
3 4 99
0 0 0 0
0 0 0 0
0 0 0 1
// 3 : 가로 길이, 4 : 세로 길이, 99 : 인벤토리에 있는 블럭의 수
// 그 이하 칸은 각 블럭의 높이 설정출력 :
2 0
// 2 : 걸린 시간, 0 : 땅의 높이[ 규칙 ]
- 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.
- 걸린 시간이 같을 경우, 높이가 더 높은 값을 출력한다.
- 블럭을 부수는 작업은 시간이 1초 소요되고, 인벤토리에 1개의 블럭이 추가된다.
- 블럭을 쌓는 작업은 시간이 2초 소요되고, 인벤토리에서 1개의 블럭이 사라진다.
[ 백준 ]
- 브루트포스 알고리즘
- 출처 : https://www.acmicpc.net/problem/18111
< 풀이 >
- 입력 받은 블럭의 높이 중 최저 높이와 최고 높이를 받아 반복문을 돌렸다. 예를 들어 블럭들의 높이 중 최저가 40이고 최고 높이가 60이라면 40 ~ 60의 모든 수를 높이로 설정하고, 해당 높이에서 조건이 맞는지 확인하는 식으로 수행하였다.
[ 코드 ]
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class BaekJoon18111 { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String s = bf.readLine(); StringTokenizer st = new StringTokenizer(s); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int min=256; int max=0; int time=0; int inven, answertime, answerheight; answertime = -1; answerheight = -1; int[][] field = new int[n][m]; for(int i=0;i<n;i++){ st = new StringTokenizer(bf.readLine()); for(int j=0;j<m;j++) { field[i][j] = Integer.parseInt(st.nextToken()); if (min > field[i][j]) min = field[i][j]; else if (max < field[i][j]) max = field[i][j]; } } inven = b; for(int height=min;height<=max;height++) { // 최소값 ~ 최대값 사이 값을 높이로 설정하여 모두 계산 time = 0; // 각 높이 계산마다 시간 초기화 inven = b; // 각 높이 계산마다 인벤토리 초기화 for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if (height <= field[i][j]) { // 현 블록이 높이보다 높을 경우 = 블럭 빼기 time += (field[i][j]-height)*2; // 높이 차이*2만큼 시간 더하기 inven += (field[i][j]-height); // 높이 차이만큼 인벤에 넣기 } } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if (height >= field[i][j]) { // 현 블럭이 높이보다 낮을 경우 = 블럭 쌓기 time += (height-field[i][j]); // 높이 차이만큼 시간 더하기 inven -= (height-field[i][j]); // 높이 차이만큼 인벤에서 빼기 } } } if ((answertime == -1)&&(inven >= 0)) { answertime = time; answerheight = height; } if ((answertime >= time)&&(inven >= 0)&&(time>0)) { answertime = time; if (answerheight < height) answerheight = height; } } System.out.println(answertime + " " + answerheight); } }
해당 문제는 반례 모음을 꼭 보고 하기 바란다.
반례 덕에 최저값(min) 설정이나 걸린 시간이 동일할 경우 더 높은 높이를 출력하기 등에서 많은 문제가 있었고, 아예 전제 자체를 잘못한 경우도 있었다.
문제를 풀기 위해서 위의 경우를 제외하고 2가지 경우를 더 생각해보았다. 1가지는 최소 시간의 높이가 이미 설치되어 있는 블럭의 높이에서 나온다라는 전제와 전체 블럭의 높이 평균값이 최소 시간의 높이이다라는 2가지를 갖고 문제를 풀었을 때 당연하게도 틀린 전제임을 깨달았다.
위의 문제는 가능한 모든 경우의 수를 모두 탐색하면서 요구사항에 충족되는 결과만을 가져온다라는 완전 탐색 알고리즘을 이용하였다.
Author And Source
이 문제에 관하여([ Java ] 18111번 - 마인크래프트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@knh4437/백준-18111번-마인크래프트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)