문제

마인크래프트

풀이

시간초과 2트를 해서 결국 다른 분들 코드를 보았다.

1. 블록의 범위가 가장 작고, 가장 큰 부분을 갱신해준다

// 블록이 가장 낮은 것이 0이고 가장 높은것이 256 개이다
int min = 0, max = 256;

for (int i = 0;i < n; i++) {
	for (int j = 0; j < m; j++) {
    	map[i][j] = Integer.parseInt(st.nextToken());
        // // 범위가 가장 작고 큰 것을 갱신해준다
        min = Math.min(min, map[i][j]);
        max = Math.max(max, map[i][j]);
    }
}

2. 위에서 적용한 [min-max] 사이에서 가장 작게 블록과 높이를 갱신할 수 있도록 합니다.

for (int h = min ; h <= max; h++) {
	int remove = 0; // 삭제 블럭 개수
    int add = 0; // 추가 블럭 개수
    int block = b; // 블록의 개수
    
    for (int i = 0;i < n; i++) {
    	for (int j = 0; j < m; j++) {
        	// 현재 높이보다 작으면 블럭을 추가 해준다
        	if (map[i][j] < h) {
            	add += h - map[i][j];
                block -= h - map[i][j];
                
            // 현재 높이보다 크면 블럭을 삭제 해준다
            } else if (map[i][j] > h) {
            	remove += map[i][j] - h;
                block += map[i][j] - h;
            }
        }
    }
    
    // 블록이 모자라면 더 큰 높이로 하기로 한다
    if (block < 0) {
    	continue;
    }
    
    // 블럭 삭제시 2초가 필요하고 추가는 1초가 필요하다
    int time = remove * 2 + add;
    
    // 걸린 시간이 적으면 높이와 시간을 갱신해준다 
    if (time <= seconds) {
    	seconds = time;
        height = h;
    }
}

전체 코드

전체 코드