전체 글 (347) 썸네일형 리스트형 [KOI] 백준 2666 - 벽장문의 이동 icpc.me/2666 문제 이해와 그 접근 어떤 벽장을 사용하려는데 열려있다면 추가 비용 없이 그대로 이용할 수 있다. 만약 닫혀있다면 사용을 위해 벽장문을 밀어야 하는데 초기에 열린 벽장이 두개 주어지므로 닫혀있는 벽장을 열 수 없는 경우는 없다. 증명은 생략. 그렇다면 벽장문을 미는 경우는 두개로 나뉘어진다. 왼쪽으로 밀던가 오른쪽으로 밀던가. 동적계획법을 통해 이 두가지의 경우를 적절히 탐색하여 최소 비용을 찾아내면 될 것이다. 구현 dp 테이블을 이차원으로 구성했다. dp[i][j] := i번째 벽장을 열려고 하고 벽장이 j와 같은 상태일 때(비트마스크) 최소 비용 탑다운 dp를 통해 왼쪽으로 미는 비용과 오른쪽으로 미는 비용을 비교해서 최솟값을 구하면 된다. 각 방향마다 벽장문을 몇개 밀어야 .. 백준 2410 - 2의 멱수의 합 icpc.me/2410 이 문제는 DP 중에 유명한 유형인 동전 교환문제이다. $2^x$의 가치를 가진 동전이 무한히 있는 것으로 생각할 수 있다. dp 테이블은 다음과 같이 정의된다. dp[n] = 원소들을 모두 합해서 n이 되는 집합의 갯수 점화식은 다음과 같이 계산한다. $dp[n] += dp[n - 2^x]$ $n - 2^x$에서 $2^x$를 더하면 n이 되므로 이전에 계산된 $dp[n - 2^x]$를 모두 더하는 방식으로 dp[n]을 구할 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #define mod 1000000000 using namespace std; i.. 백준 1965 - 상자 넣기 icpc.me/1965 생각을 하다보면 LIS의 형태를 띄고 있음을 눈치챌 수 있다. $n \leq 1000$ 이므로 이진탐색을 쓰던 DP를 쓰던 LIS의 길이를 구해주자. 백준 2092 - 집합의 개수 icpc.me/2092 1 이상 T 이하의 값을 가진 수 A개가 주어지면 개중에 K개 뽑아서 집합을 만들 때 각 집합의 원소 개수가 S 이상 B 이하인 집합의 개수를 구하는 문제이다. (순서가 다른 것은 같은 것으로 친다.) 이 문제는 푼 사람이 얼마 안되지만 부분집합 개수와 관련된 연산을 하는 문제는 dp의 주요 유형중 하나이다. Solution 일단 A개의 원소들을 각 수가 몇 개 존재하는지 기록하자. 구현에서는 배열을 사용하였다. dp 테이블은 이차원으로 설계한다. dp[n][k] -> n 이하의 값을 가진 수 중에서 k개를 선택해 집합을 생성하는 경우의 수 이때 공집합을 인정하여 dp[0][0] = 1이다. 1부터 T까지 반복문을 돌면서 단일 숫자로 집합을 생성하는 경우(ex {5}, {5, 5}.. 백준 1738 - 골목길 icpc.me/1738 문제 분석 가는 길마다 돈을 갈취당하거나 주울 수 있다. 갔던 곳을 또 가도 똑같은 일이 일어난다. 최적의 경로는 보유금을 최대로 한 채로 콘도에 도착하는 경우이며 최적의 경로에 도달할 수 없는 경우가 있다고 한다. 다음을 생각해볼 수 있다. 1. 콘도에 못가는 경우 : 당연하게도 경로 자체가 없으면 콘도에 갈 수 없다. 2. 가는 길에 돈을 얻는 사이클이 있는 경우: 민승이는 최대 보유금을 위해 돈을 줍느라 최대 보유금은 양의 무한대로 발산하므로 콘도에 영영 도착할 수 없게 된다. 이 내용들을 고려하여 금액을 가중치로 바꾸면 음수의 가중치를 처리할 수 있는 알고리즘이 필요하다. 벨만포드/SPFA로 풀어보자. 구현 콘도에 갈 수 없는 경우를 미리 처리해주자 $n \leq 100$ .. 이전 1 ··· 59 60 61 62 63 64 65 ··· 70 다음
