DP (57) 썸네일형 리스트형 [Python] 15488번 나이트가 체스판을 벗어나지 않을 확률 https://www.acmicpc.net/problem/15488 15488번: 나이트가 체스판을 벗어나지 않을 확률 첫째 줄에 N, 나이트의 좌표 x, y, 이동 횟수 K가 주어진다. (1 ≤ N ≤ 50, 1 ≤ x, y ≤ N, 0 ≤ K ≤ 50) www.acmicpc.net 23/08/18 확률DP 문제로, 이 유형을 처음 접해봤기 때문에 복습을 해보고자 글을 작성한다. 첫 번째 접근 방식: 처음 접근 방식은 BFS를 구현하여 직접 나이트를 옮기면서 나올 수 있는 확률들을 모두 곱하는 방식이었다. 이 방식은 다음과 같다. 우리는 나이트가 $K$번 이동한다는 사실을 알고 있고, 나이트가 체스판을 벗어나는 이동을 하는 순간, 그 즉시 더 이상 움직일 수 없다는 것 또한 알고 있다. 기본적인 방법은.. [Python] 24187번 Korta vokaler https://www.acmicpc.net/problem/24187 24187번: Korta vokaler Att lösa algoritmproblem är svårt, men en sak som ofta är ännu svårare är att förbereda testdatan. Ta problemet Arabiska till exempel. Här har juryn lagt många timmars intensivt arbete åt att konstruera mästerverk som hej vad heter du. En fråg www.acmicpc.net 23/07/03 언어 장벽이 있는 스웨덴어 문제로, 다른 사람들의 풀이와는 다르게 푼 듯 하여 올려본다. 문제 접근 방식: 먼저, 문제를 요.. [Python] 8845번 Gra https://www.acmicpc.net/problem/8845 8845번: Gra Dla każdej konfiguracji początkowej w osobnej linii wypisz "W", jeśli Hektor wygra grę przy danym ustawieniu, "P" w przeciwnym przypadku. www.acmicpc.net 23/05/31 스프라그-그런디 정리가 적용되는 게임은 DAG(Directed Acyclic Graph)로 모델링 될 수 있다는 사실을 알고 있다면 쉽게 풀 수 있는 문제이다. 비슷한 문제들로 다음과 같은 문제들을 추천하니, 풀어본다면 좋은 연습이 될 것이다. https://www.acmicpc.net/problem/10363 10363번: Circ.. [Python] 27306번 DAGame https://www.acmicpc.net/problem/27306 27306번: DAGame 첫 번째 줄에 노드의 개수를 나타내는 정수 $N$ ($2 \le N \leq 500$), 간선의 개수를 나타내는 정수 $M$ ($1 \leq M \leq 100\,000$)이 주어진다. 두 번째 줄 부터 $M$개의 줄에 서로 다른 두 정수 $p$, $q$ ($1 \leq p$ www.acmicpc.net 23/05/03 스프라그-그런디 정리에 대한 이해도가 있어야 해결할 수 있는 문제다. 몇몇 사람들은 스프라그-그런디 정리의 문제를 풀 때 결과만 외우고 그냥 XOR계산만 적용해서 문제를 푸는 경우가 좀 있다고 생각한다. 나도 스프라그-그런디 정리를 적용한 문제를 처음 풀었을 때, 이해 없이 결과만 받아들이고 문.. [MatKor] Math is difficult 문제 수학을 좋아하는 하늘이는 수학을 싫어하는 재우에게 문제를 냈다. $i \in \mathbb{N}$과 $\alpha , \beta \in \mathbb{N}$에 대하여 $0 < a_i < a_{i+1}$와 $\alpha a_i < a_{i+2}$, 그리고 $a_{i+2} \equiv \alpha a_i (\mathrm{mod} \ \beta a_{i+1})$, $a_i \in \mathbb{N}$을 만족하는 수열 $\{ a_i \}$가 있다. 이때 자연수 $N$이 주어질 때, 위의 조건을 만족하는 수열 중 $a_N$을 최소로 만드는 수열을 $f(N) = \{ a_1, a_2, \cdots , a_N \} $라고하자. 또한, 이러한 $f(N)$에 대하여 원소의 합을 $S(N) = \sum_{i = 1}.. [Python] 2758번 로또 https://www.acmicpc.net/problem/2758 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 23/03/13 전형적인 2차원 DP문제로, 만약 DP가 아니라 백트래킹으로 접근한다면 시간초과가 날 수도 있을 문제이다. 문제 접근 방식: $\mathrm{DP}$문제를 접근할 때에는 먼저 상태를 정의하는게 우선이다. 이 문제에서는 영향을 미치는 요소가 $n$과 $m$ 두가지 라는 사실을 알 수 있다. 때문에 다음과 같이 상태를 정의해보자. $\mathrm{DP}[i][j]$ $=$ 선영이가 지금까지 $.. [Python] 1229번 육각수 https://www.acmicpc.net/problem/1229 1229번: 육각수 육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, ..., n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다. 그림 1 그림1은 h1, h2, h3, h4를 의미하며, www.acmicpc.net 23/03/09 조금은 독특한 방식의 DP문제로, 문제에서 주어진 정보를 적극 활용하여 미리 전처리를 해 시간을 대폭 줄여야 하는 문제이다. 만약 문제에서 주어진 정보가 없었더라면 조금은 더 까다로웠을 지 모른다. 이전에 도전했다가 시간초과를 여러 번 받아 실패했던 문제로, 이 글을 통해 도움을 받았으면 좋겠다. 문제 접근 방식: 이 문제는 캡틴 이다솜 문제와 유사한 방.. [Python] 2421번 저금통 https://www.acmicpc.net/problem/2421 2421번: 저금통 홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다. 홍태석은 www.acmicpc.net 23/03/12 전형적인 2차원 DP문제로, 현재 상태를 잘 정의하고 점화식을 세우면 쉽게 해결할 수 있다. 문제 접근 방식: 문제를 보고 처음에 발견한 사실은, 첫번째 저금통에 돈을 넣거나 두번째 저금통에 돈을 넣거나 둘 중 하나의 상태로만 갈 수 있다는 사실을 알아냈다. 이를 통해 $\mathrm{DP}[i][j]$ $=$ 첫번째 저금통에 $i$원을 넣고, 두번째 저금통에 $j$원을 넣었을 때, 소수.. 이전 1 2 3 4 5 6 7 8 다음
