일정한 높이의 땅을 만드는데 최소 시간과 땅높이 구하는 문제다...
일단 풀긴 풀었는데 코드가 너무 더러워서 코드 정리를 해보겟슴..
기존 코드ㅋㅋ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class P18111 {
static int N, M;
static long B;
static int[][] block;
static int time, height;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //세로
M = Integer.parseInt(st.nextToken()); //가로
B = Long.parseLong(st.nextToken()); //가지고 있는 블록
time = Integer.MAX_VALUE;
height = 0;
int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE;
block = new int[N][M];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < M; j++) {
block[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, block[i][j]);
min = Math.min(min, block[i][j]);
}
}
int diff = max - min;
for(int i = 0; i <= diff; i++) { //높이 차이만큼 반복
int t = 0; //총 시간 계산
long b = B; // 블럭 수
for(int j = 0; j < N; j++) {
for(int a : block[j]) {
if(a > min) {
t += (a - min) * 2; //땅 제거 : 2초
b += (a-min); //제거한 땅만큼
}else if(a < min){
b-= min - a; //땅 쌓기 : 1초
t += (min - a); //쌓은 땅만큼 인벤토리에서 빼기
}
}
}
//공통 : 인벤토리에 블럭이 0 이상이고
if(t < time && b >= 0){ //시간이 최소이면 갱신
time = t;
height = min;
}else if(t == time && b >= 0){ //시간이 같으면 땅 높이 값 더 작은 것으로 갱신
height = Math.max(height, min);
}
min++; //땅높이 한 칸 올림
}
System.out.println(time + " " + height);
}
}
⚒️ 수정 후 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class P18111 {
static int N, M;
static long B;
static int[][] block;
static int minHeight = Integer.MAX_VALUE;
static int maxHeight = Integer.MIN_VALUE;
static int optimalTime = Integer.MAX_VALUE;
static int optimalHeight = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //세로
M = Integer.parseInt(st.nextToken()); //가로
B = Long.parseLong(st.nextToken()); //가지고 있는 블록
block = new int[N][M];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < M; j++) {
block[i][j] = Integer.parseInt(st.nextToken());
maxHeight = Math.max(maxHeight, block[i][j]);
minHeight = Math.min(minHeight, block[i][j]);
}
}
for(int target = minHeight; target <= maxHeight; target++) {
calculateTime(target);
}
System.out.println(optimalTime + " " + optimalHeight);
}
private static void calculateTime(int target) {
int time = 0; //총 시간 계산
long blocks = B; // 블럭 수
for(int i = 0; i < N; i++) {
for(int a : block[i]) {
int diff = a - target;
if(a > target) {
time += diff * 2; //땅 제거 : 2초
blocks += diff; //제거한 땅만큼
}else if(a < target){
blocks += diff; //땅 쌓기 : 1초
time += -diff; //쌓은 땅만큼 인벤토리에서 빼기
}
}
}
if(blocks >= 0){//공통 : 인벤토리에 블럭이 0 이상이고
if(time < optimalTime){ //시간이 최소이면 갱신
optimalTime = time;
optimalHeight = target;
}else if(time == optimalTime){ //시간이 같으면 땅 높이 값 더 작은 것으로 갱신
optimalHeight = Math.max(optimalHeight, target);
}
}
}
}
- 시간 계산하는 함수를 따로 빼기
- 차이만큼 반복해서 min++ 하지 않고 애초에 범위를 min ~ max로 설정
- 땅을 제거하거나 쌓는 수를 계속 계산하지 않고 변수에 저장해서 재사용
'[ STUDY ] > CodingTest' 카테고리의 다른 글
백준 30804 : 과일 탕후루 (0) | 2024.12.11 |
---|---|
BFS, DFS 어려워여 (1) | 2024.12.07 |
백준 1927 : 최소 힙 (3) | 2024.11.26 |
백준 1260 : DFS와 BFS(오늘의 교훈 : 문제를 잘 읽자) (2) | 2024.11.25 |
11727 : 2 x n 타일링2 (DP) (0) | 2024.11.24 |