본문 바로가기

PS/BOJ57

백준 1866 / C++ https://www.acmicpc.net/problem/1866 1866번: 택배 첫째 줄에 배송해야 할 물품의 개수 N이 주어진다. (1 ≤ N ≤ 3,000) 둘째 줄에는 각 물품의 목적 지점의 번호가 빈 칸을 사이에 두고 주어진다. 지점의 번호는 10,000 이하의 자연수이다. 셋째 줄에 www.acmicpc.net [ 풀이 ] 관찰을 통해 인접한 값들끼리, 그리고 그 거리들이 멀수록 헬기로 옮기는게 좋음을 알 수 있다. 정렬한 후 앞에서부터 트럭으로 옮길지 헬기로 옮길지 정해주자. 또한 옮기는 위치도 결정해줄 수 있다. d1, d2 , .... , di를 골라서 옮겼다고 할 때 헬스가 x지점에 내려주면 트럭으로 움직여야 하는 거리는 f(x)=sum(|x-d_i|)가 된다. 이 함수는 중간지점에서.. 2022. 8. 18.
백준 5463 / C++ https://www.acmicpc.net/problem/5463 5463번: 건포도 플로브디브의 유명한 초콜릿 가공업자 Bonny는 가로 M개, 세로 N개의 격자에 건포도들이 들어있는, N*M크기의 건포도 초콜릿을 만들었다. 각 1*1 격자에는 최소 1개 이상의 건포도가 들어있으며, 2개 www.acmicpc.net [ 풀이 ] 나눴을 때 합을 계산해주려면 시작점 좌표와 끝점 좌표를 알아야 한다. 마침 n,m도 50이하다. dp[sx][sy][ex][ey]를 (sx,sy)~(ex,ey)로 만들어지는 직사각형에서 건포도의 최소 양이라고 하자. 전이는 2가지다. 가로로 자르는 경우, 세로로 자르는 경우. 이후 식을 세우는건 쉬우므로 코드로 대체한다. [ Code ] #include using namespa.. 2022. 8. 17.
백준 1017 / C++ https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net [ 풀이 ] 홀짝성을 기준으로 이분그래프로 모델링하자. a[0]가 있는쪽을 왼쪽집합으로 두자. 전부 소수가 되게 매칭을 하려면 우선 왼쪽,오른쪽 집합 크기가 같아야 하고, 최대매칭의 크기가 집합 크기와 같아야 한다. 이제 a[0]와 매칭되는 걸 출력까지 해야되기 때문에 a[0]와 매칭될 수를 먼저 선택한다. 이제 나머지 그래프에서 최대매칭이 크기-.. 2022. 8. 17.
백준 9525 / C++ https://www.acmicpc.net/problem/9525 9525번: 룩 배치하기 체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이 www.acmicpc.net [ 풀이 ] X를 기준으로 열과 행들이 나뉜다. 나뉜 열과 행들에 각각 순번을 매겨주자. 한 칸에 룩을 놓는 행위는 그 칸의 행과 열을 매칭시켜준다고 볼 수 있다. 또한 룩은 서로 공격할 수 없으므로 한 행에 대해 한 열을 택했다면, 다른 행은 이 열을 택할 수 없으므로 결국 이분매칭에서 최대매칭수를 찾아주면 된다. 구현이 좀 복잡한데 map으로 각 칸 (i,j)에 대해 연결여.. 2022. 8. 17.

티스토리툴바