PS23 [백준] 3392 - 화성 지도 (c++) https://www.acmicpc.net/problem/3392 문제 요약직사각형이 N개 구어진다. 직사각형끼리 서로 겹칠 수 있다고 할 때 직사각형들이 차지하는 전체 면적을 구해라. 풀이 (Nlog(3e4))스위핑세그먼트 트리https://gkgkgkgkgkgkgk.tistory.com/21 [백준] 2672 - 여러 직사각형의 전체 면적 구하기 (c++)https://www.acmicpc.net/problem/2672 문제 요약직사각형이 N개 구어진다. 직사각형끼리 서로 겹칠 수 있다고 할 때 직사각형들이 차지하는 전체 면적을 구해라. 풀이 (N*(1e4))스위핑x좌표 기준으로 직사gkgkgkgkgkgkgk.tistory.com면적을 구하는 아이디어는 이 문제와 같다. 하지만 제한이 커서 세그먼트 .. 2024. 10. 30. [백준] 2672 - 여러 직사각형의 전체 면적 구하기 (c++) https://www.acmicpc.net/problem/2672 문제 요약직사각형이 N개 구어진다. 직사각형끼리 서로 겹칠 수 있다고 할 때 직사각형들이 차지하는 전체 면적을 구해라. 풀이 (N*(1e4))스위핑x좌표 기준으로 직사각형에 시작점과 끝점을 y범위와 함께 배열에 담고 스위핑으로 구할 수 있다. 모든 지점에서 직사각형에 포함된 y좌표를 모두 배열에 기록해두면(현재 점이 시작점이면+ 끝점이면-) 전 점부터 현재 점까지에 면적을 구할 수 있고 이걸 모든 점에서 해주면 된다.#include using namespace std;#define ll long longint main() { cin.tie(0)->sync_with_stdio(0); vector> a; int n;cin>>n.. 2024. 10. 30. [백준] 23044 - 트리 조각하기 (c++) https://www.acmicpc.net/problem/23044 문제 요약N개의 bool값과 정점이 N개인 트리가 주어진다. 터뜨릴 정점과 폭탄 세기(인접한 몇칸까지 터뜨릴 것인가)를 설정해서 폭탄을 터뜨릴건데 bool값이 1인 정점은 모두 터져야 하고 0인 정점은 모두 터지지 않아야 한다. 폭탄 세기의 최댓값을 구해라. 풀이 (NlogN)매개 변수 탐색BFS매개변수탐색으로 폭탄 세기를 정하고 가능한지 BFS로 알 수 있다. bool값 0인 정점을 다 큐에 넣고 bfs를 한 번 돌리면 세기가 x일 때 bool값 0인 정점에 영향을 주지 않고 설치 가능한 모든 정점을 알 수 있다. 그 정점들을 넣고 bfs 한 번 더 돌린 다음 bool값 1인 정점을 모두 방문 했는지 확인하면 된다.#include us.. 2024. 10. 14. [백준] 3362 - 수수께끼 (c++) https://www.acmicpc.net/problem/3362 문제 요약N과 K, N개의 동전 가치가 주어진다. 동전을 처음부터 연속으로 사용해서 최소 몇번 동전까지 쓰면 1~K까지 모든 가치를 만들 수 있는지 구해라. 풀이 (NlogK)매개 변수 탐색그리디동전을 정렬하고 나면 가치를 몇까지 만들 수 있는지 알 수 있다. 현재 가치를 x까지 만들수 있고 다음에 가치가 y인 동전이 오면 x+y까지 만들 수 있다. 하지만 만약 x+1#include using namespace std;#define ll long longint main() { cin.tie(0)->sync_with_stdio(0); int t;cin>>t; while(t--) { int n,k;cin>>n>>k.. 2024. 10. 11. [백준] 1800 - 인터넷 설치 (c++) https://www.acmicpc.net/problem/1800USACO January 2008 Contest > Silver 3번 문제 요약1정점에서 n정점으로 가는 경로에 포함된 k+1번째로 큰 가중치의 최소값을 구해라. 풀이 (log(1e6) * P)0-1 BFS매개 변수 탐색최대 간선이 꽤 작아서 매개변수탐색 돌릴 정도 시간이 된다. mid값 보다 더 큰 가중치를 가지는 간선의 가중치를 1 아닌 간선의 가중치를 0으로 고쳐 풀면 된다. 다익 돌려도 되고 0-1bfs 돌려도 돼서 0-1bfs로 풀었다.#include using namespace std;#define ll long longint main() { cin.tie(0)->sync_with_stdio(0); int n,p,k;.. 2024. 10. 9. [백준] 1019 - 책 페이지 (c++) https://www.acmicpc.net/problem/1019 문제 요약1부터 N까지 수에서 0~9가 몇 번 등장하는지 출력해라 풀이 (log10(N))수학Naive한 방법으로 시도하면 당연히 시간초과가 나게 된다. 문제를 좀 바꿔서 풀 수 있는데 각 자리마다 개수를 구하는 것이다. a~b에서 0~9가 몇 번 등장하는지 구해보자 a의 1의자리를 0으로 맞추고 b의 1의자리를 9로 맞추면 1~9가 각각 (b/10-a/10+1)번 등장한다. 1의 자리를 구한 다음에는 a/=10,b/=10를 해서 자를 하나 올려주고 똑같이 반복해주면 된다. 대신 (b/10-a/10+1)에 pow(10,자리)를 곱해줘야 한다. 1의자리를 맞추는 과정에서 a>b가 되면 안되기 때문에 조건문으로 a>b가 되면 반복을 종료해주면.. 2024. 10. 8. 이전 1 2 3 4 다음