뉴비의 PS 낙서장

대학에 진학하고 나서 처음으로 SCPC를 쳤다. 예선 1차는 딱히 쓸게 없어 보여서 쓰진 않았고, 2차도 간단하게 쓸거 같다.수식 같은거 잘 못쓰고 풀이를 진짜 진짜 못써서 못 알아들을 수도 있다는거 양해 부탁드립니다 ㅠㅠ 문제 5. (9:00 ~ 10:20, 0:00 ~ 1:00)문제가 처음 열리자 마자 5번 문제를 봤다.그냥 얼마나 어려운지 체크해보기 위해 문제를 확인한거고, 생각보다 어려워서 고민을 좀 했다. 보물이 있는 A정점을 Ao, 없는 A정점을 Ax, 보물이 있는 B정점을 Bo, 없는 정점을 Bx라 하자. 서브테스크 ? (모든 B는 Bo, 모든 A는 Ao)사실 문제를 잘못 읽어서 여기서부터 시작했다.여기서 해본 관찰은1. A-A 는 A가 이긴다.2. B-B 는 B가 이긴다.3. B에서 A가 ..

2601번: 도서실카펫 (acmicpc.net) 2601번: 도서실카펫 모든 사각형의 좌표는 1,000,000 보다 작은 음이 아닌 정수이고 가로 세로의 길이는 1,000,000 보다 작은 양의 정수이다. 얼룩 직사각형은 서로 겹치지 않지만 접할 수는 있다. 얼룩 직사각형과 카펫 www.acmicpc.net 알고리즘 태그 : 레이지 세그먼트 트리, 스위핑 시간 복잡도 : \(O(NlogN+MlogM)\) 각 얼룩 마다 어디에 카펫을 설치할 경우 이 얼룩이 지워진다는 것을 직사각형 모양의 범위로 표현할 수 있다. 이제 이 범위들을 가지고 스위핑을 하며 구간 업뎃을 해서 각 업뎃이 끝났을 때 마다 전체 구간의 최댓값을 구해주면 된다. #include #define x first #define y second..

https://www.acmicpc.net/problem/17493 17493번: 동아리 홍보하기 1, 4, 7번 전봇대에 전단지를 붙이면, 모든 곳에서 전단지를 볼 수 있다. www.acmicpc.net 보통 저런 문제들이 트리 dp형태인데, dp테이블을 직관적으로 세워보자. \(dp[i][0] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드는 자식들 중 한 노드에 전단지가 붙여져있을 때, 최소 전단지 수 \(dp[i][1] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드에 전단지를 붙일때, 최소 전단지 수 \(dp[i][2] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드의 부모가 전단지가 붙여져있을 때, 최소 전단지 수 이렇게 \(dp\)식을 세..