본문 바로가기
728x90

백준브실골/DP45

백준 2176, 합리적인 이동경로 개요문제 링크골드 2, Graph, DP, Dijkstra두 점 사이를 가까워지며 이동하기접근오랜만에 푸는 백준. 퇴사 후 옛 생각에 한 문제 풀어봤다. 문제는 1번 노드에서 2번 노드로 갈 때 갈수록 가까워지는 것이다.엥 그냥 플로이드-워셜이랑 비슷한거 아닌가? 근데 왜 1에서 2로 가는 경로만 묻는걸까? 싶을 수 있다. 가까워지며 이동하는 것이 헷갈리는 게념인데, 아래와 같이 생각해보자.출발점 A에서 도착점 D로 이동할때 B와 C의 갈랫길이 있다고 생각하자.D까지 거리는 B가 5, C가 10이다.A에서 B,C까지 이동거리는 모두 1이다.그럼 최적의 선택지는 A->B->D로 6이다. A의 최소 이동거리는 6이다. 이때는 도착점까지 최소 거리가 6->5->0으로 최소거리가 줄어드는 조건을 만족한다.하지만.. 2025. 1. 13.
백준 22886, Moons and Umbrellas 개요 문제 링크 골드 5, DP, Greedy CJ 또는 JC가 나타날 때마다 X,Y의 비용을 지불할 때 비용의 최솟값 구하기 접근 DP의 정석같은 문제, 끝이 C, J일때를 기준으로 DP를 돌리면 된다. 만약 현재 끝이 J라면 min(이전J, 이전C+CJ), 끝이 C라면 min(이전C, 이전J+JC)를 해주면 된다. 끝이 ?라면 각각 C, J일때에 대해 각각 생각해주면 된다. 문제가 헷갈리는 부분은 두가지인데, 문제를 그리디하게 생각해버리면서 생긴다. 그런데 완탐을 해도 문제가 없고 그리디로 생각하면 한없이 복잡해진다. 먼저 x나 y가 양수라는 가정하에는 C만 계속 연속되거나 J만 계속 연속되는 것이 이득이라 생각할 수 있다. 그래서 그리디로 접근할 수 있는데 그럴 필요가 없다. CJ또는 JC를 번갈아.. 2023. 7. 16.
백준 25097, Controlled Inflation 개요 문제 링크 골드 2, DP, Greedy N명의 P개 작업을 최소한의 조작으로 마무리하기 접근 Codejam 2022 문제, codejam 문제는 시간을 많이줘서 생각이 맞으면 크게 틀리는 일이 없다. 문제는 생각이 어려움. 해법은 완탐을 하면 되는데, 완탐 조건이 약간 까다롭다. 먼저 완탐의 방식부터 생각하면 한 구간의 시작과 끝을 기준으로 잡고 모든 (s,e)에 대해 최솟값을 구하면 된다. 즉, for (s1:start) { for (e1:end) { for (s2:start) { for (e2:end) { value[s1][e1] = Minimum(previous[s2][e2]) } } } } 이런 느낌으로 가면 되고 Minimum은 앞에있는 모든 경우를 돌아보면서 최적값을 구해주는 것이다. .. 2023. 7. 16.
백준 12783, 곱셈 게임 개요 문제 링크 골드 2, DP 숫자를 자유롭게 이어붙이고, 서로 곱하여 N을 만들 때 곱셈의 최소 횟수 접근 전형적인 재귀 DP문제, 메모이제이션이 필요하다고 생각해서 엄청 헤맸는데 메모이제이션이 필요 없다. 왜냐? 어차피 m이 20개밖에 안돼서 큰 의미가 없다. 풀이는 어떤 수 N을 "이어붙여" 만들 수 있다면 0, 아니라면 약수들에 대해 약수의 dp와 몫의 dp+1을 해주면 된다. 먼저 카드를 받아온 상태에서 set에 모든 이어 붙인 수를 저장해봤다. 메모리 초과가 난다. 그럼 어떤 수가 이어 붙인 수인지 판단하는 함수를 만들었다. 메모리 초과는 해결됐는데 96%에서 시간초과가 난다. 그럼 약수를 하나의 set에 저장해서 사용해보자. 다시 메모리 초과가 나버렸다. 그럼 마지막으로 모든 수의 약수를 .. 2023. 5. 11.
백준 2031, 이 쿠키 달지 않아! 개요 문제 링크 골드 2, DP, Bisect 길이가 D인 구간을 K개 사용해 최대한 많은 점을 덮기 접근 K가 10인게 함정인 문제. "덮는다" 에 대한 생각이 쉽지 않아서 까다로운 문제였다. 우선 어떻게 덮는게 최선인지 생각해야 하는데, 덮는 구간의 시작과 끝은 항상 N개의 점 중 하나를 포함하는 것이 이득이다. 굳이 빈 구간에 양끝점을 둘 필요가 없다. 그럼 전체 점을 정렬하고, 각 점 a[i]에 대해 a[i]-D의 위치를 lower bound로 구해두자. 그 위치를 p라고 하면, 길이가 D인 구간에 대해 i-p개의 점이 존재하는 것이다. 나머지는 knapsack이랑 비슷하게 생각하면 된다. j개의 구간을 이용해 i까지 덮는 경우를 저장한 2차원 dp[i][j]를 이용하고, 업데이트는 다음과 같이 .. 2023. 4. 5.
백준 16132, 그룹 나누기 (Subset) 개요 문제 링크 골드 4, Knapsack, DP 1부터 N까지의 수열의 부분수열의 합이 전체 합의 절반이 되도록 하는 경우의 수 접근 SSP의 Knapsack을 쓰는 문제, O(2^n)이나 O(2×2^(n/2))가 O(nS)보다 현저히 크기 때문에 Knapsack을 쓰는 게 이득이다. 시간을 비교해보자. $O(2^n)$ $O(2\times 2^{n\over 2})$ $O(nS)$ 2^50 2^26 50×(50×51/2) 1e15 6.7e7 64000 Meet in the middle로도 풀 수는 있다. 652ms가 나온다. Knapsack의 연산 횟수가 대략 1000분에 1 정도 되니 1ms가 안돼서 Knapsack은 0ms가 나왔다. 둘 다 아래에 추가해두었다. Knapsack, 배낭 문제로 이 문제.. 2023. 4. 5.
백준 21757, 나누기 개요 문제 링크 골드 2, DP, Bisect 나눈 부분 수열의 합이 모두 같도록 수열을 4덩이로 나누기 접근 DP로 푸는 방법과 이분탐색으로 푸는 방법이 있는데 일단 생각나는건 이분탐색 뿐이라 일단 이분탐색을 사용했다. 둘 다 설명해볼 테니 천천히 뜯어보자. 이분탐색 크게 어렵지 않다. 누적합이 S인 인덱스를 map에 벡터 형태로 저장한다. 인덱스는 순차적으로 저장될테니 모든 벡터는 오름차순이다. 어떤 인덱스가 전체 합의 절반 M이면, 그 앞과 뒤에 존재하는 인덱스 중에서 누적합이 M/2, M/2×3인 인덱스를 찾아줘야 한다. 그런데 앞서 map에 인덱스의 벡터를 오름차순 형태로 저장했으니, 개수를 찾기 위해 lower, upper bound를 활용하면 된다. 따라서 아래처럼 해준다. 왼쪽 개수 = m.. 2023. 3. 30.
백준 26156, 나락도 락이다 개요 문제 링크 골드4, DP, 조합론 연속에 상관없이 추출한 부분문자열 중 끝이 ROCK인 문자열의 개수 접근 DP보다는 조합론을 쓰는게 더 깔끔하고 간단하다. 핵심은 끝이 ROCK이라면, R을 선택한 위치 뒤의 R은 선택하지 않고, R을 선택한 위치 앞의 모든 문자는 스위치처럼 선택/안선택 을 결정해야 하니까 2^(자리수) 만큼의 경우가 있다는 것이다. 이게 무슨 말이냐. 아래 예시를 보자. ZROCROCK 앞의 R을 선택하면 뒤의 R은 선택하지 않는다. 그래서 뒤의 R을 선택했다면, 앞의 R을 선택하는 것은 자유이다. 따라서 뒤의 R을 선택하는 경우는 ZROC에 대해 스위치를 껐다 키므로 16개가 된다. 다음으로 O를 선택하면 앞의 모든 R의 경우의 수를 더할 수 있다. 앞O는 앞R, 뒷O는 앞R,.. 2023. 3. 29.
백준 24466, 도피 개요 문제 링크 골드4, DP 각 정점간 이동의 확률이 주어졌을 때, 9번 이동 후 가장 가능성 높은 도착 위치와 확률 구하기 접근 재밌는 문제다. 이게 소수점 18자리 출력 문제는 웬만하면 없고 대부분 6자리, 9자리 정도라서 실수하기 좋은데, 함정은 9번 이동이다. 9번이동을 하면 소수가 아닌 long long으로 처리할 수 있는데, 아래 예시를 보자 2 2 0 1 p 1 0 p 0, 1, 0, 1을 9번 왔다갔다 하게 된다. 최종 최대 확률은 (p/100)^9이 될텐데, 여기에 100^9=1e18을 곱해버리면 p^9이 되고, 이게 10^18이라면 1.+(0 18개), 아니라면 0.(p^9) 을 출력해버리면 된다. 이때 p^9이 1e18이하라서 long long 범위로 커버가 된다. 그럼 나머지는 인.. 2023. 3. 28.
백준 10109, Troyangles 개요 문제 링크 골드4, DP 모든 삼각형 모양의 개수 구하기 접근 골드 DP문제 부터 차근차근 연습해보자. 이게 문제가 현재 위치와 왼, 위, 오른쪽의 개수를 비교하는 문제인 건 바로 알겠는데, 문제는 오른쪽이 업데이트 되기 전에 현재 위치를 오른쪽과 비교해버리니 오류가 난다. 그러자고 O(N^3)을 돌리자니 시간초과가 난다. 이럴때는 왼쪽 덩이와 오른쪽 덩이를 따로 만들어 둘의 최솟값을 구해주면 된다. 왼쪽 덩이는? 왼쪽과 위쪽을 비교하고, 오른쪽 덩이는 오른쪽과 위쪽을 비교한다. 나머지는 -1인덱스 방지하기 위해 입력을 잘 해주면 크게 어렵지 않다. Pseudo code for (i=세로) for (j=가로) // 왼쪽 덩이 크기 Left = min(Left[왼],Left[위])+1 for (j=가.. 2023. 3. 28.
728x90

티스토리툴바