백준 닷컴 단계 별로 풀어보기 25단계

1단계 동전 0 (백준 11047)

• 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
• 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
• 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
• 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

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

public class Step_1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] coin = new int[n];
		for(int i=n-1; i>=0; i--) {
			coin[i] = Integer.parseInt(br.readLine());
		}
		int result = 0;
		for(int i=0; i<n; i++) {
			result += k/coin[i];
			k = k%coin[i];
		}
		System.out.println(result);
	}
}

A.

• 코인의 정보를 배열에 담아준다.
• 코인은 각 코인에 대해 배수 약수 관계이기 때문에 큰 코인부터 몫과 나머지를 이용하여 구할 수 있다.
• 각 코인에 대해 결과에는 몫을 담고 k는 나머지를 넣어서 반복문을 작성하고, 결과를 출력한다.

2단계 회의실 배정 (백준 1931)

• 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
• 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
• 첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

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

public class Step_2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		int[][] meet = new int[n][2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			meet[i][0] = Integer.parseInt(st.nextToken());
			meet[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(meet, (o1, o2)->{
			if(o1[1]==o2[1]) {
				return Integer.compare(o1[0], o2[0]);
			}
			return Integer.compare(o1[1], o2[1]);
		});
		
		int result = 0;
		int end = 0;
		for(int i=0; i<n; i++) {
			if(end<=meet[i][0]) {
				end = meet[i][1];
				result++;
			}
		}
		System.out.println(result);
		
	}
}

A.

• 끝나는 시간이 빠를수록 더 많은 회의를 진행할 수 있으니 배열을 끝나는 순서를 기준으로 오름차순 정렬한다.
• 끝나는 시간이 같다면 시작 시간을 오름차순으로 정렬한다.
• 첫 회의부터 끝나는 시간을 체크하고, 끝나는 시간 이후로 시작하는 가장 빠른 회의를 찾는다. 회의를 찾을 때 마다 결과를 +1 하고 끝나는 시간을 갱신한다.
• 결과를 출력한다.

3단계 ATM (백준 11399)

• 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
• 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
• 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

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

public class Step_3 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st= new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		int result = 0;
		for(int i=0; i<n; i++) {
			result += arr[i]*(n-i);
		}
		System.out.println(result);
		
	}
}

A.

• 인출에 걸리는 시간이 짧은 사람부터 처리를 해야 기다리는 사람의 수가 최대한 작아지기 때문에 입력받은 배열을 오름차순 처리한다.
• 배열의 각 인원의 걸리는 시간 * 남아있는 인원을 결과에 누적한다.
• 결과를 출력한다.

4단계 잃어버린 괄호 (백준 1541)

• 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
• 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
• 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
• 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
• 첫째 줄에 정답을 출력한다.

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

public class Step_3 {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		String formular = sc.nextLine();
		String temp = "";
		char one;
		int result = 0;
		boolean minus = false;
		for (int i = 0; i < formular.length(); i++) {
			one = formular.charAt(i);
			if(one == '+' || one == '-') {//연산기호가 들어오면 minus가 이전에 등장했는지 여부에 따라 result에 더하거나 뺀다.
				if(minus) {
					result-=Integer.parseInt(temp);
				} else {
					result+=Integer.parseInt(temp);
				}
				if(one == '-') {//-를 받은 이후의 모든 숫자들은 -로 연산한다.
					minus = true;
				}
				temp="";//다음 숫자를 작성하기 위해 temp를 비워준다.
			} else {
				if(one=='0'&&temp.equals("")) {//숫자의 맨 앞에 0이 오는 경우 temp에 이어주지 않는다.
					continue;
				} else {
					temp+=one;
				}
			}
		}
		if(minus) {
			result-=Integer.parseInt(temp);
		} else {
			result+=Integer.parseInt(temp);
		}

		System.out.println(result);

	}
}

A.

• 첫 - 연산 이후는 모든 연산을 -로 계산할 수 있다.
• 입력값을 char 단위로 분해하여 식을 만든다.
• 연산기호가 등장하기 전 까지의 숫자들을 묶어준다. 0이 맨 처음 등장하는 경우 무시한다.
• 연산기호가 등장한 경우 이전에 -기호가 나왔다면 결과에 묶은 값을 빼주고, 그 이외는 묶은 값을 더해준다.
• 결과를 출력한다.

5단계 주유소 (백준 13305)

• 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.
• 표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

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

public class Step_5 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long[] distance = new long[n - 1];
		long[] oil = new long[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n - 1; i++) {
			distance[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			oil[i] = Integer.parseInt(st.nextToken());
		}
		long lowPrice = oil[0];
		long result = 0;
		long tempDistance = 0;
		for(int i=0; i<n-1; i++) {
			tempDistance += distance[i];
			if(lowPrice>oil[i+1]) {
				result+=tempDistance*lowPrice;
				tempDistance=0;
				lowPrice=oil[i+1];
			}
		}
		result+=tempDistance*lowPrice;
		System.out.println(result);
	}
}

A.

• 주어지는 값이 int의 범위를 초과할 수 있으므로 long으로 수를 받는다.
• 앞에서부터 거리의 누적 합을 구한다. 기름 값이 이전의 기름 값보다 낮은 경우 거리 누적 합과 이전 기름 값을 곱한 결과를 결과에 더해준다.
• 모든 거리의 계산을 완료한 후 남은 거리와 최소 기름 값을 곱하여 결과에 더해준다.
• 결과를 출력한다.