1. 문제 """ 2 * N개의 숫자가 주어졌을 때, 겹치지 않으면서 2개의 원소가 하나의 그룹을 이루도록 하여 총 N개의 그룹을 만드려고 합니다. 적절하게 그룹을 만들어 각 그룹에 있는 원소의 합 중 최댓값이 최소가 되도록 하는 프로그램을 작성해보세요. 예를 들어 N = 2, 주어진 원소가 3, 5, 5, 2 였을 때 그룹을 [5, 5], [3, 2]로 나눈다면 각 그룹에 있는 원소의 합은 순서대로 10, 5 이므로 이 중 최댓값은 10이 됩니다. 만약 그룹을 [3, 5], [5, 2]로 나눈다면 각 그룹에 있는 원소의 합은 순서대로 8, 7 이 되므로 이 중 최댓값은 8이 되며 이보다 최댓값을 더 작게 만들 수는 없습니다. """ 2. 풀이 항상 문제부터 똑바로 이해해야돼 2N개의 숫자를 N개 N개씩..
1. 문제1 18310번: 안테나 (acmicpc.net) 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 2. 풀이 수직선 위에 위치한 점 중에서 모든 점까지 거리 합이 최소인 점의 좌표는 어떻게 찾을 수 있을까 직관적으로는 점의 좌표를 오름차순으로 정렬하고 당연히 중앙에 위치한 점이 모든 점까지 거리 합이 최소인 점일텐데 왜 그런지를 한번 생각해본다면.. 수직선 위에 집이 있을때, 맨 왼쪽 집에서부터 시작해서 오른쪽으로 한칸씩 이동한다고 생각해보자 1부터 시작해서 오른쪽으로 이동한다고 해보면... 왼쪽 집 1개와 거리가 +1 하지..
1. 문제 25947번: 선물할인 (acmicpc.net) 25947번: 선물할인 입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 $n$ ($1 ≤ n ≤ 100\,000$), 예산을 나타내는 양의 정수 $b$ ($1 ≤ b ≤ 10^9$), 반값 할인을 받을 수 있는 최대 선물의 수를 www.acmicpc.net n개의 선물 가격이 있고, 예산이 b원일때, 반값 할인을 a번 받을 수 있다면, 최대로 살 수 있는 선물의 개수는..? 2. 풀이 가장 먼저 생각한건... 가격표를 정렬하고 큰 가격부터 a개는 반값으로 할인시킨다음에, 다시 정렬하고 b원만큼 사는 것 from sys import stdin n,b,a = map(int,stdin.readline().split()) p..
1. 문제 1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 수식에 괄호를 쳐서 결과를 최소로 만드는 문제 2. 풀이 수식에 +,-만 나온다는 점을 생각하면.. 이 수식이 최소가 될려면?? +를 먼저 계산해서, 각 항을 최대로 만들어줘야한다. 그래야 -에 의해 최소가 되겠지 그래서 -로 수식을 split해주고... split된 리스트를 순회해서... 각 원소를 int()로 바꿔본다. int()로 바꿀때 에러가 나거나 나지 않거나 둘중 하나다. 에러가 나지..
1. 문제 2777번: 숫자 놀이 (acmicpc.net) 2777번: 숫자 놀이 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 양의 정수 N이 주어진다. (1 7: print(-1) continue else: prime[n] += 1 a,b = divmod(prime[2],3) if b == 2: b = 1 elif a == 2 and b == 0: a = 1 c,d = divmod(prime[3],2) answer = a+b+c+d+prime[5]+prime[7] print(answer) 2와 3의 경우에 2를 3번 곱한 8까지 압축시켜야하고 3의 경우 2번 곱한 9까지 압축시켜야하고 5,7은 그대로 두면 되고 근데 또 압축이 가능한 경우가 2*..
1. 문제 25418번: 정수 a를 k로 만들기 (acmicpc.net) 25418번: 정수 a를 k로 만들기 7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다. www.acmicpc.net 정수 a에 1을 더하거나 2를 곱해서 k를 만들때, 연산 횟수의 최솟값을 구하는 문제 2. 풀이1(BFS) 이 문제의 기본은 BFS로 푸는 것이다 정수 a에서 시작해서, delta 배열은 1,2가 있고 1이 나오면 a + 1에 가서 범위를 벗어난건지, 이미 방문했는지 검사 2가 나오면 2a에 가서 범위를 벗어난건지, 이미 방문했는지 검사 from collections import deque def bfs(..
