AndroidTeacher

www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 설명 수식이 문자열로 주어질 때, 적절한 괄호를 쳐서 수식의 결과값을 최소로 만들면 된다. 단, 처음과 숫자는 숫자이며, 두 개 이상의 연산자가 나타나지 않으며(++,--) 연산자는 +, -만 사용할 수 있다. 풀이 과정 그리디 알고리즘 문제이다. 최소값을 만들기 위해선 어떻게 해야할까? 마이너스 바로 뒤에 괄호를 열고 그 안의 수식을 최대로 만든 후 다시 괄호를 닫으면 된다. 처음 풀었던 방법은 바..

www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 설명 ATM기 앞에 사람이 N명 서있는데, 이 N명의 사람들이 돈을 인출하는데 걸리는 시간은 제각각이다. 이 때, 앞 사람의 돈을 뽑는 시간이 길 수록, 뒤에 있는 사람들의 대기 시간은 길어지게 된다. 각 사람이 돈을 인출하는데 필요한 시간(대기시간+뽑는시간)의 합의 최솟값을 구하면 된다. 풀이 과정 내가 ATM기에 줄을 서 있다고 가정해보자. 나의 대기시간이 짧아지려면 어떤 상황이 되어야 하는가? 당연히 내 앞에서 돈을 뽑는 사람들이..

www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 설명 한 개의 회의실에서 N개의 회의가 이루어진다. 각각의 회의 I에 대해 시작시간과 끝나는 시간이 주어지며, 각 회의실은 겹쳐서 사용할 수 없다. 단, 끝나는 즉시 다음 회의가 시작을 이어받을 수 있으며, 시작 시간과 끝나는 시간이 같을 수도 있다.( 시작 즉시 종료 ) 이 때, 열릴 수 있는 회의의 최대 갯수를 구하면 된다. 풀이 과정 대표적인 그리디 개념을 이용하는 문제이다. 그리디는 당장의 상황을 기준으로 확장시키는 방향으로 풀면 쉽게 해결이 가능한 경우가 많다. 내가 회의실을 사용하고 있다고 가정했을 때, 내 회..

www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 설명 N종류의 동전으로 K원을 만들 때, 동전 개수의 최솟값을 구하는 문제이다. 풀이 과정 먼저 coin 리스트에 코인들을 오름차순으로 입력받게 되는데, 가장 적은 수의 코인을 갖기 위해서는 단위가 큰 코인부터 채워야 한다. 따라서 coin을 내림차순 정렬해주고 하나씩 차례대로 계산을 해주면 된다. K원을 현재 코인으로 나눈 값의 몫을 누적해..