백준/DP (67) 썸네일형 리스트형 [KOI] 백준 2169 - 로봇 조종하기 https://www.acmicpc.net/problem/2169 힌트 1 더보기 주어진 상태 공간에서 방향을 반영한 DP 테이블을 설계할 수 있다. DP 테이블을 만들 수 있겠는가? 힌트 2 더보기 이 문제를 바텀 업 DP로 해결을 시도할 경우 2MN번 반복문을 돌아야 할 것이다. 혹시 자기의 코드가 NM번 반복문을 돌고 있을 경우 무엇을 빠트렸는지 생각해보자. 힌트 3 더보기 최장 경로를 찾아야 하면서도 입력 값에 음수가 들어간다. 혹시 DP 테이블 초기화에 문제가 있진 않는지 점검한다. 풀이 더보기 3방향으로 로봇이 움직이면서 최장 경로를 찾는 문제이다. N,M≤1000 임을 감안하여 우리는 다음과 같은 DP 테이블을 생각할 수 있다. dp[i][j][k] := k방향으로 좌표.. 백준 13555 - 증가하는 부분 수열 https://www.acmicpc.net/problem/13555 17409 - 증가 수열의 개수와 풀이가 같다. 다만 17409와 달리 원소의 상한과 수열의 길이가 불일치라는 것과 세그먼트 트리가 아닌 펜윅 트리로만 풀린다는 점을 유의하여 구현하도록 한다. 전체 코드 더보기 #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; #define mod 5000000 int n, k; int dp[51][100001]; int sum(int pos, int seq) { if (!seq) return 1; int ret = 0;.. 백준 17409 - 증가 수열의 개수 https://www.acmicpc.net/problem/17409 Intro 적당히 작은 N에 대해서는 DP[k][n] := n번째 수에서 LIS의 길이가 k인 경우의 수로 정의하여 O(KN2) DP로 해결할 수 있다고 알려져 있다. 스택 오버플로우 다만 이 문제에서는 N≤100000 이므로 무식하게 다중 반복문을 돌릴 수 없을 것이다. 어떻게 해야 할까? 아이디어 이 게시글 중반부에서 LIS를 세그먼트 트리로 구하는 법을 소개하고 있다. 이를 잘 응용하면 naive 한 DP를 수행하는데 걸리는 O(N2) 시간 복잡도를 O(NlogN)으로 줄여볼 수 있지 않을까? 우리는 세그먼트 트리를 이용하여 n 이하의 수로 이루어지고 길이가 k의 수열의 개수를 관리할 것이다... 백준 18249 - 욱제가 풀어야 하는 문제 https://www.acmicpc.net/problem/18249 아이디어 문제에서 말한 그래프를 그려보자 문제의 요구사항에 맞춰 N개의 간선을 직접 선택하다 보면 다음 사실을 발견할 수 있다. 그래프를 위 그림처럼 보고 평행한 두 정점을 한 줄이라 취급했을 때 N개의 간선을 선택하면 N번째 줄까지 도달한 상태여야 한다. 즉 N개의 간선을 선택하는 방법은 N번째 줄에 도달하는 방법과 동치이며 한 줄을 잇는 한 줄 간선이나 4개의 정점을 교차하여 잇는 쌍칼 간선을 적절히 선택하여 N번째 줄에 도달하는 방법을 생각하면 된다. 쌍칼이 아니라 대각선 간선으로만 배치하는 경우 N개의 간선을 선택할 수 없다. 우리는 이 발견으로 다음 점화식을 세울 수 있다. $f(n) = f(n - 1) + f(n - 2) \;.. 백준 2399 - 거리의 합 www.acmicpc.net/problem/2399 C 계열 언어를 쓰면 O(N2)로 뚝딱 풀 수 있지만 파이썬으로 풀어보았다. 풀이 점과 점 사이 거리를 누적합으로 저장하면 O(N)으로 모든 쌍의 거리를 저장할 수 있다. 점들의 좌표들이 정렬된 배열 ar에서 f(i−1)이 ar[i - 1]과 이전 점들의 거리 합을 나타낼 때 ar[i]와 이전 점들의 거리 합을 구하는 점화식은 f(i)=f(i−1)+(ari+ari−1)×i이다. i가 1씩 증가할 때마다 이전 점들과 ar[i] 사이의 거리를 구하기 위해 (ari+ari−1)를 지금까지 거쳤던 점들의 개수만큼 더해줘야 한다는 사실을 생각하면 $(ar_{i} + ar_{i - .. 이전 1 2 3 4 5 6 7 8 ··· 14 다음 5/14
