백준/DP (63) 썸네일형 리스트형 백준 1657 - 두부장수 장홍준 https://www.acmicpc.net/problem/1657 현재 위치에서 뒤의 몇 열을 비트 마스크로 관리하는 dp이다. 풀이의 근원은 이 포스트, 또는 이 자료를 참조하라. 이 문제는 위와 달리 칸을 선택하지 않는 경우도 있으므로 이를 고려해서 동적 계획법을 수행하면 된다. 전체 코드 더보기 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 69 70 71 72 73 74 75 76 77 78 79 8.. [KOI] 백준 10937 - 두부 모판 자르기 https://www.acmicpc.net/problem/10937 현재 위치에서 뒤의 몇 열을 비트 마스크로 관리하는 dp이다. 풀이의 근원은 이 포스트, 또는 이 자료를 참조하라. 이 문제는 위와 달리 칸을 선택하지 않는 경우도 있으므로 이를 고려해서 동적 계획법을 수행하면 된다. 전체 코드 더보기 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 69 70 71 72 73 74 75 #pragma GCC .. [KOI] 백준 2673 - 교차하지 않는 원의 현들의 최대집합 https://www.acmicpc.net/problem/2673 관찰 주어진 그림을 보자. 5~27을 무조건 연결한다고 가정하면 구간 [5, 27] 내의 점과 교차하는 현을 잇는 것은 불가능하다. 하지만 해당 구간을 벗어나는 현과는 연결할 수 있다. 다시 말해 어떤 현의 두 점이 구간 밖에 있으면 교차하지 않게 선택할 수 있다는 것이다. 아래의 그림처럼 어떤 현을 기준으로 했을 때 그 구간보다 작은 현들을 최대한 선택해야 함을 이해할 수 있다. 즉, 작은 구간에서 교차하지 않은 현의 최대 개수에서 큰 구간에서 교차하지 않는 현의 최대 개수로 누적하는 동적 계획법으로 생각할 수 있다. 헷갈리는 경우 만약 100과 1이 연결되어 있다고 해보자. 100~1의 길이는 작지만 구간으로 표현하면 [1, 100]으.. 백준 1937 - 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 다음 dp 테이블을 세운다. dp[i][j] := 좌표 (i, j)에서 시작했을 때 가질 수 있는 최장 경로의 길이 각 좌표마다 가질 수 있는 최장 경로를 DFS로 검색하면 $O(V^{2}E)$가 되어 시간 초과를 받게 된다. 이를 $O(V^{2})$로 줄여보자. 각 정점마다 DFS를 수행하면서 거쳐간 정점에 저장한 지역 최장 경로는 일단 저장한다. 그리고 이미 거쳐간 정점에 대해서는 .. [ICPC] 백준 11066 - 파일 합치기 https://www.acmicpc.net/problem/11066 다음 DP 테이블을 세운다. dp[i][j] := i번째부터 j번째 파일까지 합치는 최소 비용 4중 반복문으로 i번째 책을 시작으로 j + 1개의 연속된 책을 합치려고 하는데 pivot이 m번째 책일 때 양 옆의 책들을 합치는 비용을 계산하면서 테이블을 채우는 방법을 생각할 수 있다. 다만 연속된 책을 합치는 과정을 반복문마다 수행하면 시간 초과를 받을 위험이 있다. 누적합으로 파일을 합치는 비용을 미리 계산하면 일부 연속된 책을 합치는 비용을 $O(1)$의 시간 복잡도로 처리할 수 있으므로 3중 반복문으로 줄어든다. 주어지는 TC에 대해 3중 반복문으로 테이블을 채운 후 최소 비용을 출력하면 정답을 받을 수 있다. 전체 코드 더보기 #.. 이전 1 2 3 4 5 6 ··· 13 다음
