마인크래프트(18111)

마인크래프트(18111)

import java.io.*;
import java.util.*;

public class Main{
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
    int[] arr = new int[257];
    
    int bottom = 257, top = 0;
    
    for(int i = 0; i < n; i++){
      st = new StringTokenizer(br.readLine());
      for(int j = 0; j < m; j++){
        int num = Integer.parseInt(st.nextToken());
        arr[num]++;
        bottom = (bottom > num)? num : bottom;
        top = (top > num)? top : num;
      }
    }
    
    int time = Integer.MAX_VALUE;
    int height = -1;
    
    for(int i = bottom; i <= top; i++){
      int high = 0, low = 0; // i보다 높은 땅, 낮은 땅
      
      for(int j = bottom; j <= top; j++){
        if(arr[j] == 0 || i == j) continue;
        
        if(i > j) low += (i -j) * arr[j];
        else if (i < j) high += (j - i) * arr[j];
      }
      
      if(high + b >= low){
        int temp = (high * 2) + (low * 1);
        
        if(time >= temp){
          time = temp;
          height = i;
        }
      }
    }
    
    sb.append(time).append(" ").append(height);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close(); 
  }
}

풀이과정

1. 처음에는 각 숫자의 평균값을 구해서 기준점으로 삼았다. (예시들의 답은 평균 값에서 +1 -1 정도의 높이가 정답이었다)
2. 그래서 평균값을 기준으로만 시간과 높이를 계산하여 정답을 구하였다.
3. ‘틀렸습니다’가 출력되었기에 다시 생각해보니, 혹시나 평균, 평균+1, 평균-1 외의 다른 수가 될수도 있지 않을까란 생각에 검사 범위를 넓혔다.

• 성공
• 메모리 : 32056 KB
• 시간 : 360 ms

보안점

1. 나는 for문을 한 번 돌며, 높이보다 낮은 땅의 갯수, 높은 땅의 갯수를 동시에 구하고 그 후에 제공되는 블럭을 더하여 시간 계산을 하였다.
2. 다른 사람의 경우 높은 땅의 갯수와 블럭을 동시에 활용하여 블럭의 갯수를 연산하였고, 그 후 낮은 땅을 계산할 때, 블록의 개수를 통해 해당 높이에 대하여 근본적으로 성립할 수 없는 상황이 되면 바로 중단되는 형태로 하여 응답시간과 메모리가 더 줄어든 형태를 보았다.
3. 이번에는 문제의 직관적인 관점으로 풀기보다는 제공되는 범위 만큼의 배열을 만들고 값을 조정하며 푸는 형태를 해보는 것에 집중하였다.
4. 다음번에는 불필요하게 도는 for문을 줄일 수 있는 방법도 생각해봐야겠다.