본문 바로가기

PS/BOJ57

백준 2191 / C++ https://www.acmicpc.net/problem/2191 2191번: 들쥐의 탈출 첫째 줄에 네 정수 N, M, S, V가 주어진다. 다음 N개의 줄에는 들쥐의 x, y좌표가 주어지고, 그 다음 M개의 줄에는 땅굴의 x, y좌표가 주어진다. 모든 좌표는 절댓값이 1,000을 넘지 않는 실수이며 소숫 www.acmicpc.net [ 풀이 ] 거리가 SV 이하면 연결해주고 최대매칭을 구해주면 됩니다. 답은 N-최대매칭 이 되겠네요. [ Code ] #include using namespace std; struct pdd { double x, y; }; vectorg[111]; double s, v; int n, m, par[111], vis[111]; pdd a[101], h[101]; double.. 2022. 8. 17.
백준 14398 / C++ https://www.acmicpc.net/problem/14398 14398번: 피타고라스 수 피타고라스 수 (a, b, c)는 다음과 같은 조건을 만족하는 세 쌍이다. a, b, c는 정수이다. a^2 + b^2 = c^2 a와 b의 최대 공약수는 1이다. 영선이는 나무 막대 N개를 가지고 있다. 영선이는 직각 삼각형 모 www.acmicpc.net [ 풀이 ] 이분그래프 모델링을 해보자. 수학적 지식이 좀 필요하다. 만약 a^2+b^2=c^2에서 a, b가 짝수라면, gcd에 모순이다. a, b가 모두 홀수라면 홀수의 제곱은 4로 나눈 나머지가 항상 1이다. 따라서 c^2은 4로 나눈 나머지가 2인 짝수가 되어 모순이다. ( 제곱수는 mod4로 0,1만 가능) (원시 피타고라스 세쌍을 알고 있다면 .. 2022. 8. 17.
백준 11670 / C++ https://www.acmicpc.net/problem/11670 11670번: 초등 수학 입력과 같은 순서대로 (a,b) 순서쌍이 유효한 방정식과 함께 출력된다. 각각의 방정식은 5개의 요소로 나뉜다. a와 3개의 연산자(+ 혹은 - 혹은 *)중 하나, b 그리고 = 와 연산결과이다. 모든 연 www.acmicpc.net [ 풀이 ] 연산결과가 모두 다르게 짝지어야 한다. 이분매칭으로 해결해주면 된다. 이분그래프를 모델링할때 인덱스와 3가지 값을 연결시키면 될 것 같다. 근데 문제는 값이 음수도 나오고 큰 값이 나온다. 어차피 값의 개수는 7500개이하이므로 좌표압축으로 값의 인덱스를 연결시켜주면 된다. 이후 과정은 쉽다. [ Code ] #include using namespace std; usin.. 2022. 8. 17.
백준 1028 / C++ https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net [ 풀이 ] 한 점 (i,j)에서 왼쪽아래, 오른쪽 아래 대각선으로 최대로 긴 연속된 1의 개수를 저장해놓자. 다이아몬드의 비교는 한 점을 기준으로 min(왼쪽, 오른쪽)을 찾고 그 사이의 길이에 대해 탐색해주면 된다. 시간복잡도는 O(N^3/2)정도 된다. [ Code ] #include using namespace std; int n, m, a[777][777], dp[2][777][777]; int solve(int i, int j) { .. 2022. 8. 12.

티스토리툴바