백준/DP (67) 썸네일형 리스트형 백준 1480 - 보석 모으기 icpc.me/1480 솔루션 - 이차원 DP 더보기 테이블을 다음과 같이 정의한다. dp[i][j] := i번째 가방까지 보석의 조합을 비트마스크로 표현한 j로 채우는게 가능한가? 첫번째 가방에 보석을 채울 수 있는 경우를 비트마스크로 확인하고 다음 가방에 다른 보석을 넣는 경우를 계산한 후 m번째 가방까지 썼을 때 최대 비트를 구해 출력하면 된다. 전체 코드 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68.. 백준 2216 - 문자열과 점수 icpc.me/2216 Solution. 다음 점화식을 고려하여 탑 다운 dp로 푼다. dp[i][j] := 첫번째 문자열을 i개, 두번째 문자열을 j개 썼을 때 얻을 수 있는 최대 점수 이때 테이블의 초기화는 값이 겹치는 걸 방지하기 위해 아주 큰 값이나 아주 작은 값으로 초기화 한다. 전체 코드 더보기 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include #include #include #include using namespace std; int dp[300.. 백준 1513 - 경로 찾기 icpc.me/1513 제약이 까다로워 애를 먹었던 dp 문제이다. 오락실의 방문 순서는 순증가여야 한다는 점과 오락실은 출발점과 도착점에도 존재할 수 있다는 것이 문제를 어렵게 만든다. 다만 도시의 크기는 50 * 50이기 때문에 메모리를 넉넉하게 사용할 수 있다. 제약을 고려하여 사차원 테이블에 다음 점화식을 세울 수 있다. $f(row, \, column, \, last, \, cnt) = $ row 행 column 열에서 마지막으로 방문한 오락실의 순서 번호가 last일 때 남은 오락실 방문 가능 횟수 cnt map을 사용하여 오락실의 순서 번호를 저장한 뒤, 점화식으로 탑 다운 dp를 돌리면서 cnt번의 방문으로 학교에 도착할 수 없거나 방문했었던 오락실보다 순서 번호가 더 낮은 오락실에 방문하.. [ICPC] 백준 2159 - 케익 배달 icpc.me/2159 N명의 고객의 위치가 이차원 평면 좌표로 주어지며 그 좌표 (r, c)는 $0 \leq r, c \leq 100000$ 의 범위를 가지고 있다. 좌표의 범위가 너무나도 크기에, 선아가 배달을 하러 갈 수 있는 지역을 이차원 배열로 나타낼 수 없고 빵을 받는 고객은 자기 위치와 상 하 좌 우 한칸 떨어진 곳까지 케익을 수령할 수 있다. 또한 고객들이 주문한 순서대로 받길 원한다. 이를 통해 선아는 i번째 고객까지 배달을 했으면 무조건 i + 1번째 고객에게 가야되며 i + 1번째 고객에게 케익을 배달할 수 있는 좌표는 갈 수 없는 곳을 제외해 최대 5개가 된다고 정리할 수 있다. 즉, 선아는 다음 고객으로 갈 때 최대 5개의 좌표만 고려하면 된다. 따라서 가능한 좌표를 배열이나 벡터.. 백준 11051 - 이항 계수 2 icpc.me/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 $\binom{N}{K}$를 구하는 문제이다. $N \leq 1000$이므로 점화식 $bino(n, k) = bino(n - 1, k) + bino(n - 1, k - 1)$을 단순한 이용한 재귀를 통해서는 구할 수 없다. 메모이제이션을 통해 배열에 값을 저장하면 빠르게 계산을 할 수 있다. 전체 코드 더보기 #include #include using namespace std; int bino[1001][1001] {}; int solve(int n, int r); int main() { memse.. 이전 1 ··· 6 7 8 9 10 11 12 ··· 14 다음
