jsj0412 님의 블로그

(P1) BOJ 15983: 순간이동 발판더보기현재 시간이 $t$일 때 좌표 $c$에서 발판을 갈아타려면 기다려야 하는 시간을 계산해야 한다. 지금 밟고 있는 발판이 방문하는 좌표의 개수를 $m_1$, 갈아탈 발판이 방문하는 좌표의 개수를 $m_2$라고 하자. 또한, 좌표 $x$는 지금 밟고 있는 발판에서 $a_1$번째로 등장하고, 갈아탈 발판에서는 $a_2$번째로 등장한다고 하자. 이를 모듈러 식으로 나타낼 수 있다. 기다려야 하는 시간을 $x$라고 하면,$t+x \equiv a_1 \pmod m_1$$t+x \equiv a_2 \pmod m_2$와 같은 모듈로 연립방정식으로 나타낼 수 있다. 이러한 형태의 식은 중국인의 나머지 정리로 풀 수 있다. 이 식을 푼 다음, 다익스트라를 돌려서 최단 거리를..

문제대회 때 팀원한테 살짝 문제 설명만 듣고, 잡진 않았는데 생각보다 할 만한 문제이다. 그냥 대회때 A를 잡지 말고 이 문제를 잡을 걸 그랬다. 문제 요약:더보기수 $N$개가 주어진다. 당신은 다음 행동을 반복해야 한다.남은 수가 2개 이상이라면, 맨 앞의 수 3개 중 2개를 골라 삭제한다. 이 연산의 비용은 max(삭제하는 두 수)이다.남은 수가 1개라면, 그 수를 삭제한다. 이 연산의 비용은 삭제하는 수와 같다.모든 수를 삭제하는 데 드는 최소 비용을 구하라. 풀이:더보기그리디로 접근하는 순간 망한다. 다음과 같은 2차원 DP를 생각해 보자.$DP[i][j] = $$i$번째까지 봤을 때, $j$만 남기고 다른 수를 모두 삭제하는 데 드는 경우의 수이때, $i$번째까지 봤을 때 수가 하나만 남으려면,..

문제처음에는 "이게 풀린다고?" 싶었는데, 몇 번 관찰을 거듭하니 나름 무난했던 문제다. 문제 요약:더보기$N$명의 사람이 원형으로 앉아 있다. 한 사람이 인사를 하면, 그 양 옆에 있는 두 사람은 1초 뒤에 인사를 해야 한다. 단, 자신의 양 옆에 있는 두 사람이 동시에 인사했다면, 인사하지 않는다. 0초에 인사하는 사람의 목록이 주어질 때, $K$초 뒤 인사하는 사람의 수를 구하라. $3 \leq N \leq 2\,000\,000; 0 \leq K \leq 10^{18}$ 풀이:더보기1. 인사하는 상태를 1, 인사하지 않는 상태를 0으로 나타냈을 때, 어떤 사람의 1초 뒤 상태는 그 사람의 양옆 상태를 XOR한 값이다. 사실 당연한 말인데, 이걸 숨기려고 지문이 교묘하게 작성되어 있는 것 같다. 2..