DP (57) 썸네일형 리스트형 [C++] 28774번 Шестизначные документы https://www.acmicpc.net/problem/28774 25/01/02 백준 땅따먹기에서 나온 문제 중 하나인데, 내가 풀었을 당시에는 골드 4였으나 골드 4치고는 굉장히 어렵다고 느꼈던 문제였다. 이러한 아이디어를 복습해보고자 글을 적어본다. 문제 접근 방식: 일단 문제가 러시아어로 적혀있기 때문에 번역을 하면 다음과 같다. 회계사 발레리(Valeiry)는 회계 보고서에서 불일치를 해결하고 있습니다.그는 총 $n$개의 문서를 확인해야 하며, $i$번째 문서는 여섯 자리 정수 식별자 $a_i$를 통해 회사 네트워크에서 접근할 수 있습니다.역전(inversion)이란, 두 번호 $i$와 $j$($i 배열 ${a_i}$의 복잡성(complexity)은 여섯 자리 각각에서 발생하는 모든 역전의.. [Python] 2418번 단어 격자 https://www.acmicpc.net/problem/2418 24/11/14 예전에 북마크 해뒀다가 지금 해결한 문제다. 해결 방식은 어제 해결했던 내리막길 문제와 유사하다. 문제 접근 방식: 탑다운 DP로 접근했다. DP상태는 다음과 같이 정의했다. DP[i][j][k] = 지금까지 단어에서 k번째 글자까지 읽었고, (i, j)에 위치한 글자가 단어에서 k번째 글자일 때, 단어를 읽을 수 있는 방법의 수 이후, 모든 격자 칸을 조사하며, 이 격자 칸에 적힌 글자가 단어의 첫 글자와 일치한다면, 즉, (i, j)에 위치한 글자가 단어의 0번째 글자라면 DP[i][j][0] = 1로 초기화 해주었다. 이후 dfs를 통해 주변 8방향을 조사하며 구현했다. 우리가 원하는 값은 단어의 마지막 글자와 (.. [Python] 1520번 내리막 길 https://www.acmicpc.net/problem/1520 24/11/13 무난한 DP이다. 처음에는 바텀업으로 생각했으나, 잘 생각나지 않아서 탑다운으로 짰다. 문제 접근 방식: DP식을 다음과 같이 정의하자. DP[i][j] = $(i, j)$번째 칸에 왔을 때 항상 내리막 길로만 오는 경우의 수. 우리의 목적은 $DP[N-1][M-1]$의 값을 구하는 것이다. 또한, $DP[0][0] = 1$임을 알고 있다. 내리막 길로 간다는 것은 현재 칸보다 이전의 칸에 쓰여있는 숫자가 더 크다는 뜻이다. 따라서, 기본적으로 현재 칸을 둘러싸고 있는 4개의 주변 칸, 즉, 이전의 칸에 쓰여있는 숫자가 더 크다면, 그 칸을 통해 현재 칸으로 올 수 있다. 따라서, 4개의 주변 칸에 대해서 DP값을 찾아.. [Python] 32645번 동까뚱뽭 게임 https://www.acmicpc.net/problem/32645 24/11/11 간단한 게임이론 + 트리 DP문제이다. 문제 접근 방식: DP상태 식을 다음과 같이 정의해보자. DP[i] = $i$번째 노드에서 게임을 진행할 때 누가 이기는 지에 대한 여부 DP[i] = 0이라면 후공이 이긴다고 하고, 1이라면 선공이 이긴다고 하자. 뭐, 게임이론 많이 한 사람들이라면 스프라그-그런디로 생각해서 mex때릴 수도 있는데, 사실 게임이 하나 뿐이라서 선후공 승패 여부만 따지면 되기 때문에 간단한 게임 DP로도 풀린다. $i$번째 노드에서 밑으로 갈 수 있는 노드를 below라고 한다면, DP[below]가 모두 1이라면, 즉, 선공이 이기는 노드라면 현재 노드는 후공이 이기는 노드(즉, 선공이 지는 .. [Python] 32518번 대충 블록에서 영혼 탈출시키는 게임 https://www.acmicpc.net/problem/32518 24/11/08 간단한 탑다운 DP다. 바텀업으로는 해결할 수 없다. 문제 접근 방식: 처음에는 $N$의 제한이 $10^{18}$인 것을 보고 DP가 아니라 하나의 완성된 수식으로 나올 줄 알고 100까지의 바텀업 DP를 돌렸다. 뚜렷한 규칙이 보이지 않아서, 수학적으로 해결하는 것은 그만두고, 다른 해결방법이 있는지 모색하기 위해 어떤 경우에 최댓값이 나오고, 그때 분할되는 경우가 어떤 경우인지를 모두 찾는 코드를 작성했다. $N-2$가 3으로 나눠진다면, $((N-2)//3, (N-2)//3, (N-2)//3)$과 같이 분할된다. 예를 들어, 8과 같은 경우, 들어내는 블록을 기준으로 3개의 체인이 나오는데, 각 체인의 길이는 .. [Python] 17367번 공교육 도박 https://www.acmicpc.net/problem/17367 24/07/05 살짝 변형된 확률 DP문제이다. 기댓값의 의미를 되살리며 문제를 해결해보자. 문제 접근 방식: 모든 게임의 상태는 마지막 주사위 눈금 3개에 의해 결정되고, 주사위를 몇 번 던질 수 있는 지에 의해 결정이 된다. 따라서 4차원 확률 DP로 문제를 해결할 수 있다. 먼저 마지막 주사위 눈금 3개를 입력받으면 이에 대한 상금을 반환하는 prize(d1, d2, d3)를 구현하자. 수찬이가 받을 수 있는 상금의 기댓값이 최대가 되도록 게임을 한다는 말이 무슨 말일까? 이 말은, 현재 상태에서 수찬이가 주사위를 굴려서 상금의 기댓값이 올라간다면 주사위를 굴리고, 그렇지 않다면 현재 상태에서 얻을 수 있는 상금이 최댓값이 된다.. [Python] 17623번 괄호 https://www.acmicpc.net/problem/17623 24/07/01 업다운 랜디를 하다가 만난 문제이다. 복습 겸 의식의 흐름대로 적어보고자 한다. 문제 접근 방식: 요구 사항은 다음과 같다. 괄호 문자열은 소괄호, 중괄호, 대괄호로 만들 수 있음.괄호 문자열은 두 괄호 문자열을 서로 Concatenate하거나 하나의 괄호 문자열을 감싸면 만들 수 있음.val함수를 통해 괄호 문자열의 값을 정수로 알 수 있음.또한 dmap함수를 통해 괄호 문자열의 값을 정수로 알 수 있음.어떤 정수 $N$이 주어질 때, $val(x) = N$이 되도록 하는 괄호 문자열 $x$를 찾는 것이 우리의 목적임.이러한 $x$가 여러 개 있다면 $dmap(x)$가 최소가 되도록 하는 것이 우리의 목적임. dma.. [Python] 12070번 gNumbers (Small) / 12071번 gNumbers (Large) https://www.acmicpc.net/problem/12070https://www.acmicpc.net/problem/12071 24/05/21 스몰과 라지 풀이 방식이 거의 유사해서 같은 글로 적어보려고 한다. 문제 접근 방식: 문제 설명에 앞서서 편의 상 선공이 지는 포지션을 Cold position, 선공이 이기는 포지션을 Hot position이라고 부르겠다. 문제의 내용은 Small문제에 들어가면 wizardrabbit님이 번역해놓은 것이 있으므로 이를 참고해보자.https://www.acmicpc.net/board/view/143383 Small의 경우는 제한이 $N = 1, 000$까지이므로, DP배열을 $1,000$까지 선언하여 DP를 돌리면 된다. 이 때 어떤 숫자가 g-num.. 이전 1 2 3 4 ··· 8 다음
