10월 4째주 PS정리

shikgom2 2024. 10. 22. 01:42

2024. 10. 22. 01:42

#dsu

곧이 곧대로 구현한다면 시간초과가 난다.

관찰을 해보면, 역순으로 전개했을 때 찍힌 도장이 남아있을 것이다.

이것을 이용해 모든 칸이 한 번만 봐지게 DSU로 구현하였다.

몇일동안 생각만 한 문제였는데 https://ps.mjstudio.net/boj-14632여길 참고하였다...

#flow

grid 내에서 flow하는 문제로 생각해볼 수 있다.

이분 그래프를 source -> 가로 -> 세로 -> sink로 생각해봤을때, 장애물로 막혀있는 구간의 간선을 제거해주고 이분매칭을 돌렸을 때 최대 매칭 수는 필요한 자원의 수와 같다.

#math

x,y,z를 각각 구해보자.

(3,3,3)인 case를 생각해본다면 x,y,z는 /3한값의 곱이 된다.

(2,3,6)인 case를 생각해본다면, x//=2 , y//=3, z //=6한 값의 곱이 된다.

(2,4,4)인 case를 생각해본다면, x//=2, y//=4, z//=4한 값의 곱이 된다.

그왼 모두 -1 이다.

마라톤에 나와서 풀었는데, 많조분 너무싫다..

google