http://wwww.acmicpc.net/problem/1007 # 조건 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다. 벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다. 평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오. # 접근 방법 우선 벡터를 구하는 방법 v1 = (x2-x1, y2-y1) v2 = (x4-x3, y4-y3) 벡터 사이의 합은 v1 + v2 = (x2+x4 -x1-x3, y2+y4 -y1-y3) |v1 + v2| ..

http://www.acmicpc.net/problem/23762 23762번: 배드민턴 복식 팀 만들기 (1, 4, 2, 3), (96, 99, 97, 98) 의 두 팀을 만들고 4번, 5번을 빼는 것이 실력 차를 최소로 만들 수 있다. www.acmicpc.net # 조건 고려대학교 배드민턴 동아리원들이 배드민턴을 치려고 한다. 모두가 동시에 재밌게 배드민턴을 치기 위해, 동아리원들의 각각의 실력을 고려하여 다음과 같이 복식 팀을 만들려고 한다. 배드민턴 복식은 2명이 짝을 지어 대결하기 때문에, 양쪽에서 총 4명이 한 팀을 이루어 게임을 진행한다. 또한 모든 사람의 배드민턴 실력을 자연수로 나타낼 수 있다. 이 때 각 팀의 (실력 최댓값) - (실력 최솟값) 을 그 팀의 실력차라 하자. 비슷한 실력..

http://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net # 조건 그래프가 주어졌을 때, 그래프의 최소 스패닝 트리를 구하시오 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중 가중치의 합이 최소인 트리를 말한다. # 접근 방법 최소 스패닝 트리 = 최소 신장 트리이다. prim 또는 kruskal 알고리즘을 통해 풀어준다. https://cheon2308.tistory.com/en..

http://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net # 조건 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3..

http://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net # 조건 정수 X에 사용할 수 있는 연산은 아래와 같은 3가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오 # 접근 방법 bfs와 deque를 이용해준다. 현재 연산 횟수와 현재 수, 연산을 거쳐간 숫자를 같이 넣어준다. 1이 될 때까지 반복 bfs로도 통과했지만 2번째 코드는 dp를 이용한 코드 bfs 이용 import sys sys.s..

http://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net # 조건 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4..

http://www.acmicpc.net/problem/3096 3096번: 영화제 넓은 강이 있는 나라가 있다. 강의 왼쪽에는 마을이 N개, 오른쪽에도 N개가 있으며, 각 마을은 1번부터 N번까지 번호가 매겨져 있다. 왼쪽 마을 중 하나와 오른쪽 마을 중 하나를 연결하는 배는 총 www.acmicpc.net # 조건 강의 왼쪽, 오른쪽에는 N개의 망르이 있고 각 마을은 1번부터 N번까지 번호 왼쪽 마을 중 하나와 오른쪽 마을 중 하나를 연결하는 배는 총 M개가 있고, 양방향 연걸 상근이는 총 4개 마을에서 영화제를 개최하려고 한다. 왼쪽 마을에서 2개, 오른쪽 마을에서 2개를 고르며, 왼쪽 마을은 모두 오른쪽 마을과 배로 직접 연결되어 있어야 한다. 영화제를 개최할 마을을 고르는 방법의 수를 구하는 프..

http://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net # 조건 새 집의 크기는 N x N 격자판으로 나타낼 수 있고, 1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있고 r은 행의 번호, c는 열의 번호이며 행과 열의 번호는 1부터 시작한다. 파이프는 아래와 같은 형태이고 2칸을 차지한다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 빈 칸만 차지할 수 ..

http://wwww.acmicpc.net/problem/13172 # 조건 M개의 주사위가 있어서 이 중 i번째 주사위가 Ni면체 주사위이고 모든 면에 적힌 수를 더한 값이 Si일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다고 가정한 상태에서 모든 주사위를 각각 한 번씩 던졌을 때 나온 수들의 합의 기댓값을 구하는 문제를 만들었다. 확률변수 X의 기댓값을 E(X)로 나타내면, 기댓값의 선형성에 의해서 두 확률변수 X, Y에 대해 E(X + Y) = E(X) + E(Y)가 성립하므로, 이 문제의 답을 아래와 같이 간단하게 나타낼 수 있다. S1/N1 + S2/N2 + ... + SM/NM 즉, 각 주사위에서 나오게 되는 수의 기댓값을 모두 더하면 답이 되는 것이다...