[구현] 백준 - 마인크래프트

-문제

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

 

-자바(시간초과)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int i, j;	//반복문 변수
		
		st = new StringTokenizer( br.readLine() );
		
		int n = Integer.parseInt( st.nextToken() );	//N개의 행
		int m = Integer.parseInt( st.nextToken() );	//M개의 열
		int b = Integer.parseInt( st.nextToken() );	//인벤토리 안에 보유하고있는 블록 개수
		
		int time = 0;
		
		int[][] ground = new int[n][m];	//초기 땅 블록 담을 배열
		HashMap<Integer, Integer> hm = new HashMap<>();	//초기 땅 블록에서 높이별 개수를 세기위한 변수
		
		for( i=0; i<n; i++ ) {	//n개 줄만큼 초기블록 설정
			st = new StringTokenizer( br.readLine() );
			
			for( j=0; j<m; j++ ) {
				ground[i][j] = Integer.parseInt( st.nextToken() );
				
				//해시맵 안에 각 높이별 개수를 집어넣는다. 0이 11개고 1이 1개면 => 0: 11개, 1: 1개
				if( hm.get( ground[i][j] ) == null ) hm.put( ground[i][j], 1 );
				else hm.put( ground[i][j], hm.get( ground[i][j] )+1 );
			}
		}

		
		//해시맵에서 가장 값이 큰 키를 찾아낸다. -> 가장 많이 나오는 높이를 찾음
		int max_value = 0;
		int max_ground = 0;	//가장 많이 나오는 높이 변수
		
		for( Integer k : hm.keySet() ) {
			if( max_value < hm.get(k) ) {
				max_value = hm.get(k);
				max_ground = k;		//64가 가장 많이나왔으면 64가 저장된다.
			}
		}
		
		
		a:for( i=0; i<n; i++ ) {
			for( j=0; j<m; j++ ) {
				
				//땅 높이 배열의 값이 가장많이나온높이(64)보다 크면 인벤토리에 차이를 저장하고 블록을 빼준다.
				if( ground[i][j] > max_ground ) {	
					int cha = ground[i][j] - max_ground;
					b += cha;
					time += 2*cha;
					ground[i][j] -= cha;
					continue;
				
				//땅 높이 배열의 값이 가장 많이나온 높이(64)보다 작으면 인벤토리에서 1을 빼고 블록을 쌓아준다. 
				//이때 인벤토리가 0이면 땅 높이 배열의 값을 평평하게 해야되는 높이로 바꿔준다.
				} else if( ground[i][j] < max_ground ) {
					if( b > 0 ) {
						b -= 1;
						ground[i][j] += 1;
						time += 1;
						j -= 1;
						continue;
					} else {
						max_ground = ground[i][j];
						i = -1;
						continue a;
					}
				}
			}
		}
		
		bw.write( time + " " + max_ground + "\n" );
		bw.flush();
		
		bw.close();
		br.close();
	}

}

-자바(정답)

package implementation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ18111 {
    public static void main(String[] args) throws IOException {
        //풀이의 큰 틀은 각 층마다 땅을 고르는 데 걸리는 시간을 구한다.
        //0층: x초 / 1층: y초, ....
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer( br.readLine() );

        int n = Integer.parseInt( st.nextToken() );
        int m = Integer.parseInt( st.nextToken() );
        long b = Long.parseLong( st.nextToken() );

        int[][] map = new int[n][m];

        int max_floor = Integer.MIN_VALUE;

        for( int i=0; i<n; i++ ) {
            st = new StringTokenizer( br.readLine() );
            for( int j=0; j<m; j++ ) {
                map[i][j] = Integer.parseInt( st.nextToken() );

                //입력받을 때마다 가장 높은 층을 찾아낸다.
                max_floor = Math.max( max_floor, map[i][j] );
            }
        }

        
        //가장 높은 층에서 0층까지 내려가면서 시간을 구한다.
        int ans_floor = 0;
        int ans_time = Integer.MAX_VALUE;
        int store_cnt, put_cnt;

        for( int h=max_floor; h>=0; h-- ) {
            store_cnt = put_cnt = 0;

            for( int i=0; i<n; i++ ) {
                for( int j=0; j<m; j++ ) {
                    //현재 층인 h보다 클 경우 인벤토리에 넣을 store_cnt 개수 증가
                    if( map[i][j] > h ) {
                        store_cnt += map[i][j] - h;
                    }
                    //현재 층인 h보다 작을 경우 인벤토리에서 꺼낼 put_cnt 개수 증가
                    else {
                        put_cnt += h - map[i][j];
                    }
                }
            }

            //만약 인벤토리에 블록이 없다면 층을 낮춰서 다음 층으로 이동
            if( store_cnt + b - put_cnt < 0 ) continue;

            //윗층의 걸린시간보다 현재 층 걸린시간이 적다면
            if( store_cnt*2 + put_cnt < ans_time ) {
                ans_time = store_cnt*2 + put_cnt;
                ans_floor = h;
            }
           
        }

        //최종적으로 최소시간과 층을 출력
        System.out.println( ans_time +" "+ ans_floor );

    }
}

-파이썬(pypy3로 해야지 통과)

import sys

n, m, b = map( int, input().split() )

lists = []

for _ in range(n):
    lists.append( list( map(int, input().split() ) ) )


        
#가장 높은 층을 구함
high = max( max(lists) ) 
low = min( min(lists) )
          
time = 9223372036854775807
height = 0

#가장 높은 층에서 0층까지의 땅을 평평하게 했을 때 시간구하기
for k in range(high, low-1, -1):
    x = 0 #x는 인벤토리에 넣을 블록개수
    y = 0 #y는 인벤토리에서 꺼낼 블록 개수
    
    for i in range(n):
        for j in range(m):
            #기준층보다 블록이 많으면 인벤토리에 넣을 블록개수 증가
            if lists[i][j] > k: 
                x += lists[i][j] - k
            #기준층보다 블록이 적으면 인벤토리에서 꺼낼 블록개수 증가
            else:
                y += k - lists[i][j]
    
    #인벤토리에 넣을 블록개수 + 인벤토리 - 필요한 블록개수
    if x+b - y < 0:
        continue
    
    #현재 층의 시간이 전에 층보다 작으면 time과 height를 초기화해준다.
    if (2*x + y) < time:
        time = 2*x + y
        height = k

print( time, height )