-
[백준/JAVA] 2805ETC/Algorithm 2023. 5. 20. 13:49
import java.io.*; import java.util.StringTokenizer; 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)); StringTokenizer st; st = new StringTokenizer(br.readLine(), " "); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); int[] trees = new int[N]; int max = 0; int min = 0; st = new StringTokenizer(br.readLine(), " "); for (int i = 0; i < N; i++) { trees[i] = Integer.parseInt(st.nextToken()); if (trees[i] > max) { max = trees[i]; } } while (min < max) { int mid = (max + min) / 2; long sum = 0; for (int height : trees) { if ((height - mid) > 0) { sum += height - mid; } } if (sum < M) { max = mid; } else { min = mid + 1; } } bw.write(String.valueOf(min - 1)); bw.flush(); } }
이분 탐색이 필요한 문제였다. 거기에 자료형 까지...?
아래는 시간 초과가 뜬 코드다.import java.io.*; import java.util.Arrays; import java.util.StringTokenizer; 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)); StringTokenizer st; st = new StringTokenizer(br.readLine(), " "); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); st = new StringTokenizer(br.readLine(), " "); int[] trees = new int[N]; for (int i = 0; i < N; i++) { trees[i] = Integer.parseInt(st.nextToken()); } // 시작은 나무들 중에 가장 큰 값으로 시작한다. for (int i = Arrays.stream(trees).max().getAsInt(); i > 0; i--) { // 계속해서 나무를 잘랐을 때의 총 합을 초기화 한다. int sum = 0; // 나무의 개수만큼 반복한다. for (int tree : trees) { // 만약 나무가 자르려는 높이보다 크다면 잘라보고 그 높이를 합에 추가하고 // 아니라면 그냥 넘어간다. if (tree > i) { sum += (tree - i); } else continue; // 자르고 난 후의 나무의 높이가 원하는 길이를 얻었거나 더 얻었으면 루프 탈출 if (sum >= M) { bw.write(String.valueOf(i)); break; } } // 루프 탈출 if (sum >= M) { break; } } bw.flush(); } }
솔직히 그냥 2중 반복문 써서 생각없이 짠 코드였는데....
역시나 시간 초과가 떠버렸다.
거기에 sum 값이 int 형이였는데 계속 틀렸다고 뜨길래
조건에 읽어보니 범위가 억 단위 이길래 자료형을 long 타입으로 변경하고
제출하니 해결되었다....
다음부터는 조건을 잘 읽고 생각하며 풀어야겠다.