DP (60) 썸네일형 리스트형 [Python] 2533번 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 24/03/30 예전에 해결했던 문제인데, 복습하는 겸 글을 적어본다. 문제 접근 방식: 문제의 요구사항은 트리가 주어질 때 얼리 어답터의 수를 최소화하는 문제다. 얼리 어답터가 아닌 사람들은 주변의 모든 사람들이 얼리어답터인 경우에 아이디어를 수용한다. 목표는 모든 사람이 아이디어를 수용하도록 하고 싶을 때, 얼리 어답터의 수를 최소화하는 것이다. 전형적인 트리 DP로 해결할 수 있는데, 다음과 같이 DP테이블을 정의하자. $DP[i][0]$ $=$ $i$번째 노드가 서브트리의 노드고, $i$번째 노드가 얼리 어답터가 아닐 때 서브 트리 전체의 최소 얼리 어답터 수$DP[i][1]$ $=$ $i$번째 노드가 서브트리의 노드고, $i$.. [C++] 1952번 [모의 SW 역량테스트] 수영장 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 25/02/06 전형적인 DP문제이다. 제한이 작아서 백트래킹으로도 해결할 수 있다. 문제 접근 방식: 문제의 요구 사항은 각 달의 이용횟수가 주어지고, 하루 이용권, 한 달 이용권, 세 달 이용권, 1년 이용권의 가격이 주어질 때 수영장을 이용할 수 있는 최소 비용을 구하는 것이다. 나는 다음과 같이 생각했다. 어차피 1달, 3달, 1년 이용권은 중간에 사용할 수 없다. 정확히 말하면 중간에 사용하는 것이 손해이다. 예를 들어, 내가 1월에 5번 이용해야 하는데 하루는 하루 이용권을 사서 이용하고, 나머지 4일은 1달 이용권으로 이용.. [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)를 구현하자. 수찬이가 받을 수 있는 상금의 기댓값이 최대가 되도록 게임을 한다는 말이 무슨 말일까? 이 말은, 현재 상태에서 수찬이가 주사위를 굴려서 상금의 기댓값이 올라간다면 주사위를 굴리고, 그렇지 않다면 현재 상태에서 얻을 수 있는 상금이 최댓값이 된다.. 이전 1 2 3 4 ··· 8 다음
