조준장 개발자 생존기

문제 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net - 어떤 나라에 N개의 도시가 있다. - 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. - 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. - 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. - 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. - 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. -..

문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net - 정렬된 두 묶음의 숫자 카드가 있다. - 각 묶음의 카드의 수를 A, B라 하면 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. - 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. - 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 고르는 순서에 따라서 비교 횟수가 매우 달라진다. - 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤..

문제 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net - 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. - 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. - 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. - 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. - 수열의 모든 수는 단 한 번만 묶거나, 아니면 묶지 않아야 한다. - 수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합의 ..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net - 회의실에 최대한 많은 회의를 배정하는 문제이다. - 배정된 회의는 서로 겹치지 않아야 한다. - 두 회의의 시작시간과 종료시간은 겹쳐도 된다. - 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. - 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다. 알고리즘 - 회의 수를 입력받는다. - 반복문을 통해 회의의 시작시간과 종료시간을 입력받는다. - 회의 시작시간 기준으로 정렬하고 회의 종료시간 기준으로 다시 정렬한다. - 반복문을 통해 회의 시작시간과 종료시간을 비교한다. - 이때, 시작시간이 종료시간보다 크거나 같으면 회의를 배정한다...

문제 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net - 신규 사원 채용은 1차 서류심사, 2차 면접시험으로 이루어져 있다. - 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. - 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. - 위 조건을 만족시키면서, 신규 사원 채용에서 선발할 수..

문제 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net - 하나의 양팔 저울을 이용하여 물건의 무게를 측정한다. - 무게가 양의 정수인 N개의 저울추가 있다. - 저울추를 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 문제이다. - 예를 들어, 무게각 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. - N은 1 이상 1,000 이하이다. - 각 추의 무게는 1 이상 1,000,000 이하이다. 알고리즘 - 저울추의 ..

문제 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net - 설탕은 3킬로그램 봉지와 5킬로그램 봉지가 있다. - 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지의 최소 개수를 구하는 문제이다. - 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 봉지 3개와 3킬로그램 봉지 1개를 배달해 총 4개를 가져갈 수 있다. - N킬로그램일때 3 ≤ N ≤ 5000인 정수이다. - 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다. 알고리즘 - 우선적으로 5킬로그램 ..

문제 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net - 캠핑장은 연속하는 20일 중 10일 동안만 사용할 수 있다. - 캠핑장을 연속하느 P일 중, L일 동안만 사용할 수 있다. - 강산이가 V일짜리 휴가를 시작했을 때, 캠핑장을 최대 며칠 동안 사용할 수 있는지를 구하는 문제이다. - 다음 조건을 만족한다. (1 < L < P < V) - 입력은 여러 개의 테스트 케이스로 이루어져 있고 L, P, V를 순서대로 포함하고 있다. - 마지막 줄에는 0이 3개가 주어진다. 알고리즘 - 입력은 여러 개 의 ..

문제 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net - 양수와 +, - , 그리고 괄호를 가지고 식을 만들었는데 괄호를 모두 지웠다. - 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 문제이다. - 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있다. - 가장 처음과 마지막 문자는 숫자이다. - 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. - 수는 0으로 시작할 수 있다. - 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 알고리즘 - 식을..

문제 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net - 잔돈에는 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있다. - 언제나 거스름돈 개수는 최소한의 잔돈으로 받는다. - 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈의 개수를 구하는 문제이다. - 타로가 지불할 돈은 1이상 1000미만의 정수이다. 알고리즘 - 문제는 매 상황에서 항상 최선의 선택만 하는 문제로, 그리디 알고리즘 문제라고 볼 수 있다. - 타로가 지불할 돈을 입력한다. - 타로가 ..