https://www.acmicpc.net/problem/2236 2236번: 칩 만들기 당신은 칩을 만들기 위해 기판에 N개의 부품을 장착했다. 각각의 부품을 작동시키기 위해서는 전원을 연결해야 하는데, 기판에 연결할 수 있는 전원 선이 K개 밖에 없었다. 당신은 이 K개의 전원 www.acmicpc.net 1. Logic 선을 하나의 칩에 연결하면 제곱, 두개의 칩에 연결하면 연결한 두 칩의 중요도를 제곱한다. 어떤 경우든 항상 제곱하는게 이득이기 때문에 그냥 정렬해서 큰거만 k개만큼 뽑아주면 된다 풀면서도 이게 맞나 싶었다ㅋㅋㅋㅋㅋㅋ 2. Code #include using namespace std; int n, k; vector input; queue q; int trace[51]; int mai..
그리디
https://www.acmicpc.net/problem/20310 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 1. Logic 사전순으로 가장 빠른 것을 구하라고 했기 때문에 0은 뒤에서부터 없애주고 1은 앞에서 부터 없애주는게 가장 작은 숫자를 구할 수 있는 방법이다. 2. Code #include using namespace std; int zero; int one; int checkErase[501]; int main() { string str; string ans = ""; cin >..
https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 1. Logic 자기가 예상한 등수랑 다르면 불만도가 생기기 때문에 자신의 예상 등수를 입력받은후 정렬한다. 테스트 케이스로 예를 들면 1 5 3 1 2 > 1 1 2 3 5 1 ~ 5등까지 나오기 때문에 작은것부터 숫자를 맞춰주면 된다. 코드를 보면 더 이해가 잘 갈것이다. 2. Code #include #include #include using namespace std; vector vec; int ..
https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 1. Logic - 집중국의 수신 가능 영역을 최소화 시키기 위해서는 집중국을 세울수 있는 갯수로 지어진 k만큼 다 세워 줘야 한다. 센서를 세우는데 가장 적합한 위치는 오름차순 정렬을 했을 때 인접한 두 센서의 가운데에 세워야 한다. 케이스에서 나온 1 6 9 3 6 7 > 오름차순 정렬 1 3 6 6 7 9 > 인접한 두 노드의 거리를 빼주기 dist : 2 3 0 1..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 1. Logic multiset 해설 1. 우선순위큐에 보석의 가치와 무게 순으로 넣는다. 2. 가방의 무게를 입력받아 multiset으로 넣는다. 3. multiset은 오름차순으로 정리되기 때문에 lower bound(O(logN))을 활용하여 보석의 무게와 같거나 더 큰 가방을 찾는다 vector 해설 1. 보석과 가방을 벡터에 입..
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 1. Logic 처음 생각은 긴 문자열부터 첫번째 짜리부터 순서대로 9, 8, 7 이렇게 큰 숫자부터 넣어주면 된다고 생각했지만 문자가 중복되게 나오는 경우의 수도 있기 때문에 고려를 해주어야 한다. 예를 들어 ABC BCA 같은 경우가 대표적인데, 이때는 A와 B중 어느 알파벳에 9를 할당해 줄 지 구해야 한다. 각 자릿수에 가능한 숫자를 구해보면 A=100 B=10 C=1 > 100A 1..
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. Logic 항상 작은 값 2개를 선택해서 정렬해야 최소한으로 비교할 수 있게 된다. 우선순위 큐는 우선순위가 높은 값을 기준으로 즉 값이 큰 거부터 내림차순으로 정렬해 주는 자료구조이다. 우선순위 큐를 선언과 동시에 greater인자를 붙혀주게 되면 오름차순으로 정렬되기 때문에 문제를 풀기 적절한 자료구조이다. 2. Code #include using namespace std;..
https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 1. Logic - 0에서부터 왔다가 돌아와서 책을 다시 가져가야 하기 때문에 모든 (경로값 * 2)를 하게된다. 그렇기 때문에 입력을 모든 값중 절댓값이 가장 큰 경로에 있는 책을 제일 마지막에 가져다 놓아서 * 2를 하지 않아야겠다는 생각을 했다. 1, 양수를 저장하는 positive배열과 음수를 저장하는 negative 배열을 받아서 각각 저장하며 절댓값을 통해 절댓값이 가장 큰 값을 저장해놓는다..
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 1. Logic 1. 1은 어떻게 계산 하던지 자기 혼자 더하는게 무조건 이득 2. 양수는 무조건 큰숫자부터 곱해서 더하고 혼자남으면 그냥 혼자 더히기 3. 음수는 절댓값이 큰 숫자부터 곱해서 더하고 혼자 남으면 그냥 더하기 or 0이 있으면 넘어가기 4. 0은 -1이 없거나 음수의 갯수가 짝수면 필요없지만 -가 홀수면 음수를 없애는데 사용 2. Code #include using namespa..
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 1. Logic - 해당 문제는 주어진 배열을 앞에서 부터 풀이하게 될 경우 최댓값까지 배열을 돌고 또 최댓값을 구해서 배열을 돌아야해서 이중 for문을 사용하게 되어 시간복잡도가 O(n^2)이지만 뒤에서부터 풀이하게되면 다음값을 보고 최댓값인지 알 수 있기 때문에 O(n)으로 풀 수 있다. 최악의 경우를 생각 해 봤을 때 10000 *999999 곱하게되면 int 의 범위를 훨씬 넘..
