반응형 ps연습장14 백준 4225번 : 쓰레기 슈트 (C/C++) 백준 4225번 백준 1708번 : 볼록 껍질 직관적으로 생각했을때, 쓰레기의 한쪽면이 쓰레기통의 벽에 닿아있는것이 최선의 경우이다. 오목한면은 해당되지 않음으로 우선 볼록 껍질을 구해준다. 다음 각각의 변에서 가장 거리가 먼 점까지의 거리중 가장 짧은 것을 구해주면 된다. 점 (x1, y1) 을 지나는 직선 ax+by+c = 0을 구한다음 점과 직선사이 거리 공식을 적용해주었다. 혹시나 부동 소수점 오차가 날까봐 d를 제곱한 값을 비교해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52.. 2023. 5. 17. 백준 7869번 : 두원 (C/C++) 백준 7868번 두원 3가지 경우가 있다. 한원이 한원을 포함하는 경우 안겹치는 경우 일부분이 겹치는 경우 1의 경우에는 작은원의 넓이를 출력하고, 2의 경우는 0을 출력한다. 3의 경우는 코사인 공식을 이용하여 세타 값을 구해서 넓이를 구해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #define fio() \ ios_base::sync_with_stdio(0); \ cin.tie(0) using namespace std; typed.. 2023. 5. 16. 백준 16437번 : 양 구출 작전 (C/C++) 백준 16437번 주어진 문제상황은 DAG이고, 최종 목적지가 1번이다. 따라서 위상 정렬을 적용해볼 수 있다. 늑대의 수를 음수로 표현하고, 양의 수를 양수로 표현한다. 문제에서 늑대들은 이동하지 않는다고 했으므로 노드가 양수가 되었을때, 다음 노드로 넘겨주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #define fio() \ ios_base::sync_with_stdio(0); \ cin.tie(0) using namespace std; typedef long long ll.. 2023. 5. 9. 백준 2533번 : 사회망 서비스(SNS) (C/C++) 백준 2533번 최소 얼리 어댑터의 수를 구하는 문제이다. 전형적인 트리dp문제라고 볼 수 있다. 이문제를 풀기 위해서는 트리는 트리로 구성되어있다는 개념을 이용해야한다. 우선 k=1을 얼리 어댑터, k=0인 경우를 얼리 어댑터가 아닌 경우라고 할때, dp 배열을 아래와 같이 정의한다. dp[n][k] : n이 k이고, n을 루트로하는 서브트리의 최소 얼리 어댑터의 수 1. k=1일때, 자식 노드들이 1이여도 되고, 0이여도된다. n의 모든 자식 노드를 nx라고 할때, 다음이 성립한다. 2. k=0일때, 모든 자식 노드들이 1이여야만 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34.. 2023. 5. 9. 이전 1 2 3 4 다음 반응형
