'DP' 태그의 글 목록

2022. 4. 1. 02:21 Algorithm/BOJ

문제 링크 http://icpc.me/2449 2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 풀이 오랜만에 되게 재밌게 푼 dp문제다. 3차원 dp로 풀었는데 다른 사람 코드 구경하면서 2차원 dp로 내 풀이보다 훨씬 쉽게 풀 수 있는 걸 발견했다. 이 글에선 3차원 풀이를 작성하겠다. 시간 복잡도는 O(N^3 * K)에 해결할 수 있다. dp[l][r][i] : 구간 [l, r]을 i로 만들었을 때 최소 경우의 수 a[i] : a번째 전구의 색 위와 같이 정의를 하면 세 가지 케이스로 점화식을 세..

[백준] 7620 편집 거리

2022. 3. 24. 18:11 Algorithm/BOJ

문제 링크 http://icpc.me/7620 7620번: 편집 거리 가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는데 사용한 글자를 출력한다. (출력할 글자 www.acmicpc.net 풀이 dp 역추적을 하는 문제다. 하지만 메모리를 특이하게 관리해야 하는 처음 보는 문제다. 역추적을 하기 위해서 dp테이블을 모두 가지고 있기엔 테이블의 크기가 17000 * 17000 * 4byte로 너무 크다. 그렇기 때문에 역추적을 위한 테이블을 17000 * 17000 * 2bit로 만들어 메모리를 최적화시켜야 한다. 역추적 테이블은 unsigned char 한 칸에 비트 연산을 이용하여 정보를 4개..

[백준] 1126 같은 탑

2022. 2. 26. 16:39 Algorithm/BOJ

문제 링크 http://icpc.me/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 풀이 dp문제다. dp인 것을 못 알아차리고 고민하다가 알고리즘 분류를 봤다. 처음 생각했던 점화식은 dp[i][a_size][b_size] : i번째 까지 봤을 때 a기둥의 사이즈와 b기둥의 사이즈로 dp를 정의하는 것이었다. 그러나 이 풀이는 52 * 5e5 * 5e5로 시간초과가 발생할 것이다. 그래서 a기둥과 b기둥의 높이를 더 컴팩트하게 정의할 수 있는 방법을 생각했다. 결론은 더 큰 기둥의..

[백준] 2662 기업투자

2022. 2. 23. 16:20 Algorithm/BOJ

문제 링크 http://icpc.me/2662 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 풀이 배낭 문제라고도 불리는 웰노운인 knapsack문제다. dp를 이용하여 풀 수 있다. dp[i][j] = max(dp[i - 1][j - k] + arr[k][i]) (0

[백준] 9465 스티커

2022. 1. 25. 20:53 Algorithm/BOJ

문제 링크 http://icpc.me/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 dp문제다 dp[i][0] = max(dp[i-1][1], dp[i-2][1]) + arr[i][0] dp[i][1] = max(dp[i-1][0], dp[i-2][0]) + arr[i][1] 점화식은 위와 같다. 코드 #include using namespace std; const int N = 1e5 + 5; int arr[N][2], dp[N][2]; int main() { cin.tie(0)-..

[백준] 2096 내려가기

2022. 1. 25. 14:36 Algorithm/BOJ

문제 링크 http://icpc.me/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 메모리를 줄여서 사용해야 하는 dp문제이다. dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + arr[i][j] dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + arr[i][j] 위와 같은 점화식을 세울 수 있다. 점화식을 계산할 때 이전층까지의 정보만이 필요하기 때문에 전부 기억할 필요가 없다. 코드 #include u..

백준[1562] 계단 수

2022. 1. 9. 22:28 Algorithm/BOJ

문제 링크 http://icpc.me/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 비트마스크 dp문제다. dp[자릿수][마지막 수][사용한 수]로 정의하면 dp[i][j][k | (1

백준[15678] 연세워터파크

2021. 11. 23. 15:04 Algorithm/BOJ

문제 링크 http://icpc.me/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net 풀이 세그먼트 트리로 dp최적화를 하는 문제다. dp[i] = max(dp[i], max(dp[i - k]) + arr[i]) (1 1) using namespace std; using ll = long long; const int N = 1e5 + 5; ll dp[N]; ll tree[4 * N]; ll query(int node, int s, int e, int qs, in..

백준[1010] 다리 놓기

2021. 11. 7. 18:49 Algorithm/BOJ

문제 링크 http://icpc.me/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 조합을 이용하여 풀 수 있다. 고등학교 때 확통 공부를 해봤다면 아주 자주 볼 수 있는 문제다. 다리가 겹치지 않아야 하기 때문에 오른쪽의 어떤 다리에 연결할지만 정한다면, 왼쪽 다리가 어느 다리랑 연결될지는 알아서 결정이 되게 된다. 그렇기 때문에 mCn을 하면 된다. 코드 #include int dp[32][32]; int dpf(int n, int k) { int &ret = dp[n][k]; if (n ..

백준[13976] 타일 채우기 2

2021. 10. 5. 12:37 Algorithm/BOJ

문제 링크 http://icpc.me/13976 13976번: 타일 채우기 2 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 풀이 dp와 분할 정복을 이용하여 풀이할 수 있다. 분할 정복을 이용한 행렬의 빠른 거듭제곱은 곱셈을 풀면서 공부하자. dp점화식은 dp[n] = 3*dp[n-2] + sum(dp[k]) (k는 n-4부터 0까지 k-=2) 위의 식에 n-2를 대입한식과 위의 식을 빼면 dp[n] = 4 * dp[n-2] - dp[n-4]가 나온다. 행렬식으로 표현하면 위와 같이 표현할 수 있다. 이제 위의 행렬식을 분할정복을 이용하여 빠르게 계산하면 된다. 코드 #include #include using namespace st..

백준[17070] 파이프 옮기기 1

2021. 9. 15. 16:34 카테고리 없음

문제 링크 http://icpc.me/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 풀이 dp를 이용하여 풀 수 있다. dp[x][y][state] : (1, 1)에서 가장 오른쪽 아래 점 (x, y)까지 state(가로, 세로, 대각선)로 올 수 있는 개수 코드 #include #include int arr[20][20]; int dp[20][20][3], n; bool check(int y, int x) { // 대각선 체크 if (!arr[y + 1][x] && ..

백준[1657] 두부장수 장홍준

2021. 9. 10. 15:10 Algorithm/BOJ

문제 링크 http://icpc.me/1657 풀이 비트 마스크를 하면서 dp를 돌면 된다. 백준[1648] 격자판 채우기와 거의 유사한 문제이다. 위의 문제와 차이점은 현재 칸을 안 채우고 넘어가는 경우가 있는 것이다. 코드 #include using namespace std; int dp[15 * 15][1 s[1]) swap(s[0], s[1]); if (s[0] == 'A') { if (s[1] == 'A') return 10; if (s[1] == 'B') return 8; if (s[1] == 'C') return 7; if (s[1] == 'D') return 5; if (s[1] == 'F') return 1; } else if (s[0] == 'B') { if (s[1] == 'B') r..

백준[1648] 격자판 채우기

2021. 9. 10. 14:15 Algorithm/BOJ

문제 링크 http://icpc.me/1648 1648번: 격자판 채우기 준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다. 세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노 www.acmicpc.net 풀이 비트 마스킹을 하며 dp를 돌면 풀 수 있다. 위와 같은 타일이 있을 때, k 번째 타일을 놓기 위해 필요한 정보는 k + 1 번째 타일이 채워져 있는지 여부와 k + 6(m) 번째 타일이 채워져 있는지 여부이다. 이와 같이 k번째 타일을 채우기 위해서는 m개의 타일 정보만 가지고 있으면 된다. 그렇기 때문에 m개의 타일 정보를 비트 마스킹하며 채워나가면 된다. 코드 #include #include int ..

백준 [2494] 숫자 맞추기

2021. 9. 5. 17:24 Algorithm/BOJ

문제 링크 http://icpc.me/2494 2494번: 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10 www.acmicpc.net 풀이 dp를 역추적하는 문제다. 백준 13392 방법을 출력하지 않는 숫자 맞추기 이 문제에서 역추적만 포함하면 된다. dp를 호출할 때 왼쪽 자식에서 왔는지 오른쪽 자식에서 왔는지 체크를 해주면서 함수를 호출하면 된다. 코드 #include #include using namespace std; struct T { int x, y, m; }; char from[10004]; char to[10004]; int dp[..

백준[13392] 방법을 출력하지 않는 숫자 맞추기

2021. 9. 3. 16:50 Algorithm/BOJ

문제 링크 http://icpc.me/13392 풀이 dp를 이용하여 풀이할 수 있다. 처음에 문제를 보자마자 든 생각은 dp[현재 숫자]로 1차원으로 정의하려 했지만 이렇게 했을 시 dp테이블이 10^10000 크기를 가져야 하므로 바로 패스했다. 그렇다면 현재 숫자를 가벼운 정보를 가지고 구할 수 있어야한다. 현재 내가 보고 있는 i번째 숫자를 알기 위해서 필요한 정보는 0 ~ i-1번째 숫자를 맞추는 동안 왼쪽으로 몇 번을 돌렸는지를 알아야 한다. 그렇기 때문에 dp를 정의할 때 왼쪽으로 돌린 횟수를 가지고 있어야 한다. 또한 왼쪽으로 10번을 돌리면 다시 자기 자신으로 돌아오기 때문에 (왼쪽으로 돌린 횟수) % 10의 정보만 가지고 있으면 된다. dp[i 번째 숫자 나사를 돌림][0 ~ i -1번..

티스토리툴바