Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

PS/BOJ

(3)

/<30326> Heap Structure - TOPC 2023 주간이 아닌 회고록에 쓰던 문제들을 문제 단위로 나눠서 올리게 될거 같습니다. 이유는 몰아서 쓰다 보니 좀 힘든 감도 있었고. 짧게라도 자주 쓰는 습관을 들이고 싶은거도 있고. 분량이 너무 긴가? 에 대한 스트레스도 안 받아도 되고. 팀 연습 하다가 만난 문제인데 셋에서 업솔빙 한 문제중 유일하게 마음에 드는 문제였네요.

$k$ 번째로 작은 값이 들어 갈 수 있는 정점에 대해 두가지 성질을 관찰 해야 합니다. 편의를 위해 모든 값이 unique하다고 가정합시다.루트의 깊이를

$1$ 이라 했을 때, 깊이가

$k$ 이하여야 한다. (어떤 정점의 조상들에 속한 값은 전부 그 정점에 속한 값보다 작아야 하기 때문)그 정점을 루트로 하는 서브트리의 크기를

$s$ 라 했을때

$s - 1 \le n - k$ 를 만족해야 한다..

2023.06.24 골랜디 [A] 텔레포트 3 - boj 12908번 우선 두 점 (xi, yi) 와 (xj, yj) 사이 점프로 이동해서 걸리는 시간은 | xi - xj | + | yi - yj | 입니다. 이 점을 활용해 임의의 두점 사이 걸리는 시간을 O(1)에 계산할수 있습니다. 텔레포트의 갯수가 3개로 고정되어 있기 때문에 텔레포트를 타는 모든 6C3 개의 조합에 대해 답을 계산 해주면 대충 6!=720개 정도의 조합이 나오고 각 조합에 대한 경로를 O(1)시간에 구할수 있기 때문에 충분히 빠르게 답을 구할수 있습니다. 6C3 개의 조합을 전부 돌아보는 과정은 C++의 next_permutation함수를 이용해 쉽게 구현할수 있습니다. #include using namespace std; #define endl '\n' ..

2023.06.22 양갈래 골랜디 스터디 그룹 모 양갈래를 좋아하는 디코 서버에서 방학 기간동안 매일 3문제씩 골5,4 랜디를 하자! 라는 계획을 서버장이 추진하게 되어서 시작했습니다. 할때마다 블로그에 정리하려 하는데 매일 쓰다보면 풀이 퀄리티가 떨어지는 날도 있을수 있으니 더 궁금하면 댓글로 달아주세요. [A] 유닛 이동시키기 boj - 2194번 정직하게 2차원 격자에서의 BFS를 구현해주면 됩니다. 다만 주의할점은 격자를 벗어났는지 벗어나지 않았는지 판정할때 움직이는 점의 크기가 a x b 크기이기 때문에 경계를 계산할때 조금 조심해줘야 합니다. #include using namespace std; #define endl '\n' #define PRECISION 0 #define fr first #define sc second using ll..

티스토리툴바