2026 3월 1주차 PS 기록

17615

https://www.acmicpc.net/problem/17615

 

공을 모두 한쪽으로 모아야 하기 때문에 빨간공 또는 파란공을 사용하여 왼쪽 또는 오른쪽으로 모는 경우를 모두 수행해준다.

이때, 색깔이 다른 공들이 한번에 뛰어넘을 수 있도록 한쪽 방향으로 순서대로 옮기는 모습을 상상하며 풀면 된다.

너무 어렵게 생각해서 오히려 풀이가 떠오르지 않았던 문제이다.

 

 

17614

https://www.acmicpc.net/problem/17614

 

문자열로 변환하여 3, 6, 9의 숫자를 일일이 세어준다.

 

28324

https://www.acmicpc.net/problem/28324

 

감소하는 것은 어렵지만 증가하는 것은 쉽다. 마지막 속도는 반드시 0이어야 한다.

즉, 속도제한에 맞게 거꾸로 수행해주면 된다.

뒤에서 부터 1씩 증가하되, 속도 제한에 맞추어 자유롭게 감소할 수 있음.

 

 

2170

https://www.acmicpc.net/problem/2170

 

한쪽에서 부터 쓸 듯이 문제를 처리하는 스위핑 알고리즘.

시작점을 기준으로 정렬 후 끝점이 이후의 시작점과 연결되는지 확인하며 길이를 갱신해주면 된다.

각 선분마다 앞선 선분들과 연결 혹은 끊어짐을 확인하며 길이를 갱신해주는 방법으로 해결 가능한 문제이다.

 

 

9463

https://www.acmicpc.net/problem/9463

 

inversion counting 유형의 문제이다.

 

위쪽번호를 기준으로 맵을 만들어 아래쪽 번호를 기준으로 현재 인덱스보다 큰 인덱스와 연결된 노드가 자신의 앞쪽에 있으면 두 선분은 교차한다.

1의 인덱스는 4, 5의 인덱스는 2 이므로 2보다 큰 4가 오른쪽에 있으므로 교차

 

 

 

때문에, 세그트리를 만들어 자기보다 큰 원소의 개수를 매번 세어주면 앞서 풀었던 '달리기' 문제와 동일한 문제가 된다.

 

10090

https://www.acmicpc.net/problem/10090

 

위 문제의 기본문제 버전.

 

2300

https://www.acmicpc.net/problem/2300

 

점화식을 좀 더럽게 짠 듯.

점의 개수가 10000개이기 때문에 현재 인덱스 이전의 모든 값들을 반영하는O(N^2) dp 가 가능하다.

기지국은 반드시 통신라인 위에 있기 때문에 정사각형의 한변 길이를 결정하는 요인에는 x좌표의 차이와

현재까지의 최대 y좌표 *2이다.

새롭게 추가되는 건물마다 다른 건물과 연결하는 경우를 고려하여 모든 경우중 최솟값만을 취해주면 된다.

 

34120

https://www.acmicpc.net/problem/34120

 

이상하게 푼 듯. 뭔가 이상함