이동식 저장소

문제집을 다 풀었으니, 이제 골드2~플레5 중 많이 풀린 문제를 쭉 풀어보려 한다. ``solved.ac``에서 다음의 쿼리를 적용한다. tier:g2..p5 solved:100.. 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 사실 이 문제는 초보자 시절 감명깊게 읽었던 문제이다. 그땐 5분정도 생각하다가 모르겠어서 패스했던 기억이 난다. $N$개의 점을 각각 한 번씩만 선택해서 $N/2$개의 벡터를 만들고, 만들어진 벡터의 합의 크기의 최솟값을 구하는 문제이다. 단순하게 반복문이나 ``next_..

11378번: 열혈강호 4 첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 � www.acmicpc.net 이분 매칭 연습문제인 열혈강호 시리즈의 마지막 문제. 이번 문제는 조건이 더 까다로워졌다. 각 직원은 기본적으로 하나의 일을 할 수 있고, 벌점의 분배에 따라 일을 더 할 수 있다. 이분 매칭을 할 때 주의해야 할 점은, 일단 벌점을 생각하지 말고 직원당 한 번씩 매칭을 시도해야 한다는 점이다. 그렇지 않으면 앞에서 벌점을 다 써버려서 뒤의 직원들은 기본 1번의 매칭 기회조차 주어지지 않기 때문이다. 따라서 우선 한번씩 매..

4376번: Gopher II The input contains several cases. The first line of each case contains four positive integers less than 100: n, m, s, and v. The next n lines give the coordinates of the gophers; the following m lines give the coordinates of the gopher holes. All distances www.acmicpc.net 테스트 케이스를 입력받는 점만 빼면 2191번과 정확히 같은 문제이다. 이분 매칭으로 들쥐와 땅굴을 매칭해 주면 된다. 그런데 자꾸 틀렸습니다를 받는다. 공식 데이터(A번)와 비교해 봐도 거의 ..

요즘은 이분 매칭 문제를 풀고 있다. 1574번: 룩 어택 첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼�� www.acmicpc.net $R \times C$ 크기의 체스판에 룩을 최대한 많이 배치하는 문제이다. 이때 룩끼리 공격 가능해서는 안 된다. 룩은 자신이 위치한 행 또는 열의 모든 칸을 공격할 수 있다. 비슷한 문제로 N-Queen이 있다. 이 문제는 $N \times N$의 체스판 위에 퀸을 서로 공격할 수 없도록 최대한 많이 배치하는 문제이다. 퀸은 행과 열에 더하여 대각선까지 공격할 수 있기 때문에 특정한 형태로 모델링하기 까다롭다..

4시간동안 맞왜틀 해서 화나서 쓴다. 9577번: 토렌트 희원이가 사용하는 ACM토렌트는 하나의 파일을 공유받을 때 여러 조각으로 나누어, 조각을 지닌 시드가 접속하는 시간에 시드로 부터 일부 조각을 전송 받아 파일을 완성시키는 방법으로 파일이 www.acmicpc.net 회원들로부터 $n$개의 파일 조각을 다운로드하는 데 걸리는 최소의 시간을 구하는 문제이다. 어떤 파일 조각을 아무 회원으로부터 다운로드해도 되기 때문에, 회원에 대한 정보는 무시하고 파일 조각과 시간의 관계만 생각하자. 전형적인 이분 매칭 문제이다. 매칭하는 방향은 두 가지가 있는데, 나는 조각에 시간을 매칭했다. 각 조각을 다운로드할 시작 시각을 매칭하는데, 이때 시작 시간을 매칭하므로 그래프를 만들 때 $t_{2}$는 제외해야 한다..