본문 바로가기
728x90

백준브실골/DP45

백준 1943, 동전 분배 개요 문제 링크 골드 3, DP 전체 합의 절반을 배낭문제로 구성할 수 있는지 확인하기 접근 구성 여/부만 판단하면 되므로 동전의 사용 개수에 대해 dp에 저장하지 않고 해결할 방법을 생각해야 함. 배낭문제로 풀어주면 되는데, 사용할 값은 현재 값까지 오면서 남은 각각의 동전의 개수이고, 업데이트는 모든 동전마다 순회하면서 (현재값)-(동전가치)와 비교해주면 됨. 이게 되는 이유? 동전의 개수가 생각보다 적음. 동전의 가치는 모두 다르므로 1부터 n까지 1개씩만 있다고 할 때 총합이 100,000이하이므로 n의 최대는 sqrt(200,000) ~= 450 즉 (총합의 절반) * (동전종류) 까지 순회 돌면 되니까 50000×450번 안에 해결 가능 C언어와 달리 C++의 미친 장점, map을 사용했으나 .. 2023. 2. 8.
백준 2218, 상자 안의 구슬 개요 문제 링크 골드 3, DP 원소를 제거하며 얻을 수 있는 점수의 최댓값 접근 접근 자체는 쉽지만 출력이 까다롭고 실수하기 좋다. 일단 N=1000이므로 O(N^2)에서 해결 가능. dp[i][j]를 만든다. A상자에 i개, B상자에 j개가 있을 때 얻을 수 있는 최대 점수를 저장한다. dp[2][n] 등을 사용하면 안된다는 점에 주의할 것. 그렇다면 비교할 값은? (i-1, j), (i, j-1), (i-1, j-1) 세 개가 된다. 각각 i, j개가 있으려면 i-1번째 a를 뽑거나, j-1번째 b를 뽑거나, 둘 다 뽑는 것이기 때문. 이때 (i-1,j-1)번째는 a[i-1]과 b[j-1]을 뽑을 때 얻는 점수를 더해줘야 한다. 따라서 dp[i][j] = max(dp[i-1][j], dp[i][j-.. 2023. 2. 8.
백준 2228, 구간 나누기 개요 문제 링크 골드 3, DP M개의 인접하지 않은 부분집합의 총 합의 최댓값 접근 N,M이 작으므로 N,M에 대해서는 루프를 여러번 돌려도 상관 없음. 부분합 배열도 미리 만들어서 쓰는게 편하다. dp를 사용할 때 dp[i][k] = i번째를 포함해 (끝이 i인) k개의 집합으로 이루어진 합의 최댓값을 저장해주면 됨. 업데이트는? 앞에 있는 것들 중 k-1개의 집합을 사용한 값과 비교한다. ex) 4,-7,2,-1,5 와 같은 배열을 가정하자. i 0 1 2 3 4 a[i] 4 -7 2 -1 5 k=1 1개집합 sum[0-0] =4 sum[0-1] =-3 sum[2-2] =2 sum[2-3] =1 sum[2-4] =6 1개의 집합을 사용하는 것까지는 잘 이해할 수 있다. 이때 i=3까지 2개 집합을 .. 2023. 2. 8.
백준 2332, 전화번호 개요 문제 링크 골드 5, DP 연속된 부분 문자열의 최소 구성 횟수 접근 접근 자체는 매우 쉽지만 구현이 까다로워서 실수하기 좋음 길이 L이 100으로 작으므로 O(L×L×N) 수준에서 해결가능, N은 크므로 루프는 한 번만 돌려야하고, 루프를 돌 때 중심이 처음 문자열이 됨을 알 수 있음. 문자열 루프를 돌면서 n개의 component 중 같은 것을 찾고, 만약 같다면 component의 길이만큼 뺀 위치의 값과 비교 dp[i-component_length]+1과 dp[i] 비교해서 최솟값으로 업데이트 이때 마지막 출력 조건이 앞에서부터 component를 출력하는 것이므로 업데이트마다 앞이 어딘지, 어떤 component를 사용했는지 같이 업데이트 해야함. // 아래와 같다면 ...1234.... .. 2023. 2. 8.
백준 12887, 경로 게임 개요 문제 링크 골드 5, DP 제거할 수 있는 유효지점의 최대 개수 접근 현재 지점의 제거가능 여부를 새로운 2d array에 저장한다. dp에는 현재 지점을 포함한 최대 제거 가능 지점 수를 저장한다. 만약 '#'이면 0을 저장한다. 현재 지점을 제거하려면 앞반대쪽, 반대쪽, 뒤반대쪽에 #이 없어야 한다.// 가운데 아래를 제거할 수 없는 케이스 XOO OXO OOX OOO OOO OOO // 가운데 아래를 제거할 수 있는 케이스 OOO OOO XOO OOX즉, 2 X 2의 4개 점에서 가로 두 개만 제거할 수 있다. 대각선으로 제거해버리면 지나갈 수 없다. 만약 2 X 2의 4개 점에서 모든 4개 점이 제거 가능해도 앞반대쪽이 제거 가능하다면 현재점을 제거할 수 없다.// 이런 식으로.. 2023. 2. 8.
백준 1577, 도로의 개수 개요 문제 링크 골드 5, DP 지나갈 수 없는 길을 고려한 2차원 경로 탐색 접근 K=50 으로 작으니까 길을 지나갈 수 없는지 찾을 때는 O(k)번 해주면 된다. 를 vector에 저장하고 find 하면 되겠구나 주의할 점 : 점의 대소관계를 고려하지 않고 입력이 들어오므로 비교해서 넣어주거나 넣은것에서 4가지를 찾아줘야 한다. 4가지 = (왼쪽,현재), (현재,왼쪽), (아래,현재), (현재,아래) Pseudo code vector.push({x1,y1}, {x2,y2}) for (세로) for (가로) if (왼쪽과 현재를 잇는 선분이 vector에 있으면) 왼쪽은 더하지 마라 if (현재와 왼쪽을 잇는 선분이 vector에 있으면) 왼쪽은 더하지 마라 if (아래와 현재를 잇는 선분이 vecto.. 2023. 2. 8.
백준 25633, 도미노 넘어뜨리기 개요 문제 링크 실버 1, DP 왼쪽합이 현재 원소보다 큰 최대 부분수열의 길이 접근 구간합을 구하는 문제인가? 하면 아님. 연속합이 아니기 때문에 안 됨. N = 1000이면 O(n^2) 에서 해결할 수 있겠구나. dp를 쓰는데, (총합, 최대개수) 를 저장한다. 갱신은 언제? 앞의 것들을 탐색하면서 만약 저장된 총합이 더 큰 경우에, 개수가 더 커질 수 있다면 Pseudo code dp[i] = {i까지의 최대합, i까지의 최대개수} for (앞의 것들) if (조건1. 앞의 것까지 최대합이 a[i]보다 클 때) if (조건2. 개수가 더 커진다면) dp[i] = {앞의 최대합 + a[i], 앞의 최대개수 + 1} Source code #include using namespace std; int ma.. 2023. 2. 8.
백준 21600, 계단 개요 문제 링크 실버 1, DP 히스토그램 안에 들어갈 수 있는 계단 모양 도형의 최대 길이 접근 N = 100000 이므로 O(n)에 해결해야 함 전처리를 어떻게 하지? i번째를 기준으로 바라볼 때, dp에 지금 위치까지 놓을 수 있는 계단의 최대높이를 저장 그리고 왼쪽하고만 비교하면 됨. 비교 방식은 왼쪽 최대 높이+1 보다 크면 갱신 얼핏 O(n^2)이 필요하지 않을까 생각하기 쉬운 문제, 이게 되는 이유는 1) 왼쪽높이+1이 히스토그램 보다 낮으면 어차피 새로운 계단을 만들 수 없음. 왼쪽 계단을 그대로 가져갈 수밖에. 2) 히스토그램이 더 낮으면 왼쪽 계단을 사용할 수 없음, 대신 1~현재 높이까지 계단은 사용가능, 왜냐? 어차피 왼쪽 높이는 현재 높이보다 높기 때문. 1~h-1까지가 왼쪽 구간.. 2023. 2. 8.
백준 25421, 조건에 맞는 정수의 개수 개요 문제 링크 실버 1, DP 인접한 각 자리가 2이하로 차이 나는 n자리 수의 개수 접근 1차원 dp 이용 후 n번 갱신, dp에 저장될 값 = 끝자리가 i인 n자리 수의 개수 dp[i]에 더해줄 값 = 끝자리가 i-2~i+2인 n-1자리 수의 개수 주의할 점 = 끝자리가 0이나 10이 될 수 없으므로 범위 조절 5개 int를 더하는 것이므로 integer overflow Pseudo code // 2D for (j = i-2 ~ i+2) 끝자리가 j 인 n-1 자리수 = dp[n-1][j] dp[n][i] += 끝자리가 j인 n-1 자리수; // 1D while (n) for (i) dp[i]를 갱신 Source code #include using namespace std; const int R =.. 2023. 2. 8.
백준 21317, 징검다리 건너기 개요 문제 링크 실버 1, DP 1회까지 사용가능한 특수이동을 고려해 최소 비용 경로 구하기 접근 1회까지만 사용가능한 특수이동이 존재하므로 dp는 2차원, dp[i][0] = 사용안하고 i까지, dp[i][1] = 사용하고 i까지 나머지는 단순 2차원 dp, 1,2,3칸 이전의 값과 연산해주면 된다. 주의할 점 : 음수 인덱스 접근 안하도록 확인 Pseudo code dp[i][0] = 특수이동 없이 i까지 온 경우 dp[i][1] = 특수이동 쓰면서 i까지 온 경우 // 특수이동 없는 경우 한칸전에서이동 = dp[i-1][j] + (+1)비용 두칸전에서이동 = dp[i-2][j] + (+2)비용 dp[i][j] = min(한칸전에서이동, 두칸전에서이동) // j인 이유 = 특수이동을 쓴 경우와 안 쓴.. 2023. 2. 8.
728x90

티스토리툴바