CodeDrive

ㅌ문제:

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력:

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력:

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

풀이방법:

 해당 문제는 N개의 센서가 있을 때, K개의 그룹으로 만드는 것이 목적이다. 따라서 다음과 같은 알고리즘 순서대로 진행한다.

1. 센서들을 오름차순으로 정렬한다.

2. 각 센서들간의 차이를 구한다.

3. 각 센서들간의 차이를 내림차순으로 정렬한다.

4. 앞에서 부터 K-1개를 제외한 나머지들을 다 합한다.

문제링크:

https://www.acmicpc.net/problem/2212

문제:

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

입력:

첫째 줄에 테스트 케이스의 수가 주어진다.

각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력:

각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

풀이방법:

 greedy하게 문제를 풀어주도록 한다. 다만, greedy한 조건 내에 범위가 짧은(a와 b의 차가 작은) 것 부터 먼저 배치하도록 한다. (1,3), (1,2), (1,2) 의 경우 모두에게 책을 줄 수 있지만 추가 조건이 없다면 답이 2로 나올 수 있다.

문제링크:

https://www.acmicpc.net/problem/9576

문제:

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력:

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력:

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

풀이방법:

 모든 케이스에 대해 수행하기에는 경우의 수가 너무 많기 때문에 그리디하게 이 문제를 해결하도록 한다. 각 알파벳에 대해 가중치를 구한 뒤에 가중치가 높은 순서대로 9부터 숫자를 할당하면 된다.

 가중치는 알파벳이 있는 위치, 갯수에 따라 다르게 설정한다. ABC와 같이 있을 때, 이를 숫자로 보면 A00, B0, C와 같다. 즉 자릿수가 클수록 더 높은 가중치를 가지게 된다. 따라서 word를 순회하면서 가중치를 순회하도록 한다. 이를 dict 형태로 저장하는데, 불필요한 키들을 줄이기 위해 defaultdict을 사용하여 깔끔하게 정리하도록 한다.

 최종적으로는 가중치에 따라 값을 부여하고 합을 누적시키도록 한다.

문제링크:

https://www.acmicpc.net/problem/1339

문제:

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력:

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

풀이방법:

 우선순위 큐(heapq)를 사용해서 가방에 최대한 비싼 보석을 그리디하게 넣는다 생각하면 된다. 따라서 보석의 정보들을 무게가 가벼운 순으로 heapq를 통해서 정렬하고, 가방도 오름차순으로 정렬을 한다.

 정렬을 마친 뒤에 가벼운 가방으로부터 시작하여 해당 가방에 넣을 수 있는 보석들을 최대힙으로 다시 구현을 한 뒤에 그 최대힙에서 가장 큰 값을 뽑아 answer에 더해준다. 이와 같은 과정들을 모든 가방에 대해 수행을 하며, 최대힙과 최소힙은 계속해서 누적해서 사용하도록 한다.

문제링크:

https://www.acmicpc.net/problem/1202

문제:

2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.

출력:

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

풀이방법:

 각 학생들이 작성한 예상 등수를 바탕으로 정렬을 하고, 그와 동일하게 순위를 부여하는 것이 가장 사람들의 불만도를 최소로 하는 방법이다.

문제링크:

https://www.acmicpc.net/problem/2012

문제:

학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ...개의 정사각형으로 이루어져 있다.

상근이는 점심식사로 초콜릿을 먹는다. 이때, 적어도 K개 정사각형을 먹어야 남은 수업을 졸지 않고 버틸 수 있다. 상근이의 친구 선영이도 초콜릿을 좋아한다. 선영이는 초콜릿은 돈을 주고 사기 아깝다고 생각하기 때문에, 상근이가 주는 초콜릿만 먹는다.

상근이는 막대 초콜릿를 하나 산 다음에, 정확하게 K개 정사각형이 되도록 초콜릿을 쪼갠다. K개는 자신이 먹고 남는 것은 선영이에게 준다.

막대 초콜릿은 나누기 조금 어렵게 되어 있어서, 항상 가운데로만 쪼개진다. 즉, 정사각형이 D개 있는 막대는 D/2개 막대 두 조각으로 쪼개진다.

K개 정사각형을 만들기 위해서, 최소 몇 번 초콜릿을 쪼개야 하는지와 사야하는 가장 작은 초콜릿의 크기를 구하는 프로그램을 작성하시오. 상근이는 초콜릿을 하나만 살 수 있다. 꼭 한 조각이 K개일 필요는 없고, 여러 조각에 있는 정사각형을 합쳤을 때 K개이면 된다.

입력:

첫째 줄에 K가 주어진다. (1 ≤ K ≤ 1,000,000)

출력:

첫째 줄에는 상근이가 구매해야하는 가장 작은 초콜릿의 크기와 최소 몇 번 쪼개야 하는지를 출력한다.

풀이방법:

그리디한 방법을 사용해서 풀어야 하는 문제다.

1부터 2배씩 곱해나가면서 사야하는 가장 작은 초콜릿을 구매를 한 후, 그 초콜릿으로 부터 반으로 쪼개면서 답을 구한다.

반으로 쪼갠 후에 원하는 초콜릿 크기보다 작다면 그 크기만큼 빼주고 count를 하나 늘리고, 아직 크다면 다시 반으로 쪼개는 작업을 반복한다.

문제링크:

www.acmicpc.net/problem/2885

문제:

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력:

첫째 줄에 최소 비교 횟수를 출력한다.

풀이방법:

최소한의 비교를 하기 위해서는 계속해서 가장 작은 두 수를 골라서 비교를 하는 것이 이득이다. 따라서 python의 heapq를 사용해 최소힙을 구성한다.

heappop을 사용해서 가장 작은 두 값을 뽑아내고, 이 둘을 합친 값을 다시 heap에 넣는다. 이를 heap에 하나의 원소가 남을 때까지 반복하면 최소 비교 횟수를 얻을 수 있다.

문제링크:

www.acmicpc.net/problem/1715

문제:

주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다.

A, B, C, D, E, F에 쓰여 있는 수가 주어진다.

지민이는 현재 동일한 주사위를 N^3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N*N*N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.

N과 주사위에 쓰여 있는 수가 주어질 때, 보이는 5개의 면에 쓰여 있는 수의 합의 최솟값을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수는 50보다 작거나 같은 자연수이다.

출력:

첫째 줄에 문제의 정답을 출력한다.

풀이방법:

 주사위를 쌓아서 N*N*N 크기의 정육면체를 만들게 되면, 밖으로 노출되는 면이 가장 많은 경우는 3개인 면인 경우이다. 정육면체에서 3개의 면 주사위의 개수, 2개의 면 주사위의 개수, 1개의 면 주사위의 개수는 N에 따라서 달라지게 된다.

1. 3개의 면 주사위의 개수는 항상 위쪽 면의 꼭짓점에서만 나타나므로 N과 상관없이 4번만 등장하게 된다.

2. 2개의 면이 나타나는 주사위의 개수는 모서리에서만 나타나게 된다. 이 때 위쪽 면에서는 꼭짓점에서 이미 사용한 주사위가 있으므로 이를 제외해주고 계산해줘야 한다. 따라서 (N-1)*4+(N-2)*4개가 존재한다.

3. 1개의 면이 나타나는 주사위는 ((N-2)^2)*5+(N-2)*4 개 있다.

 주사위는 위 그림에서 나타나는 것처럼 전개도를 따라서 접게 되므로, 모든 숫자 중에서 가장 작은 3개(혹은 2개)를 골라서 최솟값을 구하면 안된다. A에 있는 숫자는 F와 만날 수 없기 때문이다. 따라서 나타날 수 있는 3개인 경우는 [(0,1,2),(0,1,3),(0,2,4),(0,3,4),(1,2,5),(1,3,5),(2,4,5),(3,4,5)]와 같기 때문에 이 중에서 가장 작은 값을 가지는 경우를 찾도록 하고, 2개인 경우는 서로 반대 면에 있는 숫자만 피하면 되므로, 이를 제외하고 계산하도록 한다.

 N이 1인 경우는 위에서 구한 케이스 구분이 필요없기 때문에 따로 처리하도록 한다.

문제링크:

www.acmicpc.net/problem/1041

문제:

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력:

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력:

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

풀이방법:

유니온-파인드 알고리즘을 사용해서 문제를 풀려고 한다. 우선 초기 게이트들은 각자 번호로 초기화를 한다. 그리고 앞으로 들어오는 비행기를 게이트에 할당하기 시작한다. 이 때 할당하는 방법은 find()함수로 진행을 하며, 비행기의 번호에 따라 가장 큰 게이트에 도킹을 한다. 즉 gi번 비행기는 gi게이트에 할당하도록 하고, 만약 gi게이트에 이미 도킹 된 비행기가 있다면 그 전 게이트(gi-1)에 할당한다. 이렇게 계속해서 할당을 하다가 0번째 게이트를 만나게 되면 더 이상 도킹을 진행할 수 없기 때문에 공항을 폐쇄한다.

문제링크:

www.acmicpc.net/problem/10775

문제:

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.

제일 왼쪽 도시에서 6리터의 기름을 넣고 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2x5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고 (3x2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1x4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다.

또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2x5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4x2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력:

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

출력:

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

풀이방법:

제일 적은 비용을 지불하기 위해서는 제일 가격이 낮은 주유소에서 남은 거리에 해당하는 기름을 다 넣어야 한다.

하지만 왼쪽에서 오른쪽으로 순차적으로 진행이 되는 것이으므로 지금까지 이동한 곳에서 가장 낮은 가격의 주유소의 기름을 넣어야 한다. 예시로 보면 다음과 같다.

- 첫 도시의 주유소에서 가격이 5이고 다른 선택지가 없고 다음 도시까지는 2km를 가야하기 때문에 10원(2x5)을 지불한다. (minP =5)

- 두번째 도시에 도착해서 가격을 보니 2원이다. 따라서 minP를 2로 바꾸고 다음 주유소까지 가기 위해 6원(3x2)을 지불한다.(minP=2)

- 세번째 도시의 가격은 4원이다. 따라서 두번째 도시에서 미리 기름을 더 넣어두고 오는 것이 이득이였기 때문에 마지막 도시까지 이동하는 것도 두번째 도시에서 넣고 와야 한다. 따라서 2원(1x2)을 추가 지불한다.

따라서 최저 비용은 18원이 된다.

이를 반복문 하나로 표현하였고, 인덱스를 편하게 맞춰주기 위해서 간격배열에 0을 임의로 추가하였다.(답에 영향을 주진 않는다.)

문제링크:

https://www.acmicpc.net/problem/13305