본문 바로가기

Problem Solving/Baekjoon OJ

(21)
[BOJ 16998] It’s a Mod, Mod, Mod, Mod World 16998번: It’s a Mod, Mod, Mod, Mod World You are given multiple problems with three integers p, q, and n. Find \(\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)}\). That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus. www.acmicpc.net 풀이가 적혀있던 노트를 겨우 찾아서 포스팅한다. ㅎㅎ ㅠ 풀이 $x\%m=x-(x/m)*m$ 임을 이용해 주어진 식을 변형하면 $ans=\frac{n(n+1)}{2}p-q\sum_{i=1}^{n}\le..
Ruby V 실력은 Diamond V..
Class 9 수준 높고 멋진 셋이지만 이 이상은 풀 엄두가 안 난다.. 나는 16998번 「It's a Mod, Mod, Mod World」를 가장 재밌게 풀었다. 정말 오래전부터 고민했던 문제인데, 8483번을 풀고 나니 쉽더라 :)
[BOJ 20188] 등산 마니아 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 무난한 트리 DP라고 생각했는데 풀고 나니 DP를 쓰지 않았더라. 나처럼 푼 사람이 거의 없는 듯해서 풀이를 한번 소개해보려 한다. (어쩐지 어렵더라) 더보기 풀이의 전체적인 틀은 트리 dp할 때와 비슷하다. dfs를 돌면서 서브 트리에 대해 문제를 해결한 다음, 이를 합쳐서 전체 트리에 대한 문제를 해결한다. 하지만 이때 서브 트리에서 전해주는 값이 조금 다를 뿐이다. 다음과 같은 상황을 가정해보자. 깊이가 $d$인 노드 $p$를 루트 노드로 하는 서브 트..
Diamond I 달성 '다이아 2 달성' 글을 올린 지 대략 한 달 만에 다시 글을 쓰게 되었다. 시험 기간을 제외하면 2~3주 정도 걸린 것 같다. 내 solved.ac 히스토리를 보면 시험이 언제였는지 한눈에 찾을 수 있을 듯하다. 시험 기간 중에는 코딩을 거의 하지 않았지만 풀고 싶거나 배우고 싶은 문제와 알고리즘들을 따로 모아 두고 틈틈이 고민했다. 이 문제들을 시험이 끝나자마자 쭉 풀어버렸고, 그래서 레이팅이 급상승한 것 같다. (물론 아직 풀지 못한 문제들도 많다.) 마지막으로 푼 문제는 제곱수의 합 2 (More Huge)으로, 출제자가 소멤 블로그에 쓴 글을 참고하여 해결했다. 세 달 전에 제곱수의 합 (More Huge)를 해결했을 때부터 풀고 싶었고 최근에 학교에서 (개인적으로) 가우스 정수를 공부하고 나서..