'DP' 태그의 글 목록 (2 Page)

2021. 9. 2. 15:46 Algorithm/BOJ

문제 링크 http://icpc.me/1509 풀이 dp를 2번 사용하여 풀이할 수 있다. palin[i][j] : 문자열 구간 i ~ j 까지가 팰린드롬인지 여부 s[i] == s[j] 이면서 i+1 ~ j-1이 팰린드롬이면 i ~ j 가 팰린드롬이다. 이렇게 구해둔 팰린드롬인지 여부를 이용하여 한번 더 dp를 돌린다. dp[i] : 1 ~ i까지 최소 분할 팰린드롬 수 if palin[i][j] == true : dp[j] = max(dp[j], dp[i - 1] + 1)로 정의 할 수 있다. 코드 #include #include using namespace std; bool palin[2503][2503]; int dp[2503]; int main() { cin.tie(0) -> sync_with_..

백준[16991] 외판원 순회 3

2021. 8. 10. 15:33 Algorithm/BOJ

문제링크 http://icpc.me/16991 풀이 비트마스크를 이용한 dp문제이며 외판원 순회와 다를 게 없다. 코드 #include #include #include using namespace std; using pii = pair; pii arr[17]; double dp[17][1

백준[5557] 1학년

2021. 8. 4. 23:32 Algorithm/BOJ

문제 링크 http://icpc.me/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 dp를 이용하여 해결할 수 있다. dp[i][j] : j번째 숫자까지 봤을 때 숫자 i를 만들 수 있는 최댓값으로 정의할 수 있다. 코드 #include using ll = long long; ll dp[22][102], arr[102], n; ll dpf(ll cur, ll idx) { if (cur 20) return 0; ll &ret = dp[cur][idx]; if (re..

백준[2225] 합분해

2021. 8. 4. 22:49 Algorithm/BOJ

문제 링크 http://icpc.me/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 dp를 이용하여 풀이할 수 있다. dp [남은 수][뺄 수 있는 횟수]로 정의할 수 있다. 코드 #include using ll = long long; ll dp[202][202], N, K; const ll mod = 1e9; ll dpf(ll n, ll k) { ll &ret = dp[k][n]; if (ret) return ret; // 남은 수와 뺄 수 있는 횟수가 0일때 1리턴 if (!n && !k) return 1; // 뺄 수 있는 횟수는 끝났는데 수가 남아있을 때 0리턴 if (n && !k) return 0; for (..

백준[1915] 가장 큰 정사각형

2021. 8. 4. 19:18 Algorithm/BOJ

문제 링크 http://icpc.me/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 dp로 해결할 수 있다. dp 점화식은 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]), (i, j는 배열 인덱스)로 정의할 수 있다. 위의 그림과 같은 예제가 있을 때 (2, 2) 인덱스에서 한 변의 길이가 2인 정사각형이 만들어지기 위해서는 왼쪽, 위, 왼쪽 위 가 모두 1이어야 한다. 이 말을 바꿔 말하면 min(dp[1][1], dp[1][2], dp[2][1]) + 1 == 1 이어야 한다. (5, 5)에서 한 ..

백준[2602] 돌다리 건너기

2021. 8. 3. 13:13 Algorithm/BOJ

문제 링크 http://icpc.me/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 풀이 dp를 이용하여 풀이할 수 있다. dp는 dp[악마다리 or 천사다리][몇 번째 패턴 문자까지 발견][몇 번째 돌다리까지 갔나]로 정의할 수 있다. 코드 #include #include using namespace std; int dp[2][22][100]; string pat, a, b; int dpf(int up_down, int pat_num, int cur_num) { int &ret = dp[up_down][pa..

백준[4013] ATM

2021. 7. 30. 16:28 Algorithm/BOJ

문제 링크 https://www.acmicpc.net/problem/4013 풀이 SCC, 유니온 파인드, 위상 정렬, dp를 이용하여 풀이하였다. 다 푼 후에 다른 사람의 코드를 보고 깨달았지만, 유니온 파인드는 굳이 사용하지 않아도 된다. 출발지점부터 순회하며 dp를 돌리면 될 것 같지만 사이클이 존재하기 때문에 그럴 수 없다. 그렇기 때문에 사이클이 없는 방향 그래프로 바꿔줘야 한다. 사이클을 제거하기 위해 SCC를 사용한다. 아래 코드는 코사라주 알고리즘을 이용하였다. 구해진 SCC를 이용하여 사이클을 하나의 큰 노드로 합친다. 나는 이때 유니온 파인드를 사용하였다. 하지만 이미 SCC들을 모두 구했기 때문에 이미 합쳐져 있는 상태여서 유니온 파인드를 사용하지 않아도 된다. scc vector의 ..

백준[2482] 색상환

2021. 7. 5. 15:47 Algorithm/BOJ

풀이 이 문제는 dp를 이용하여 해결할 수 있다. dp[N][K] = dp[N-2][K-1] + dp[N-1][K] (N: 현재 보고 있는 색, K: 현재까지 선택한 수)로 구할 수 있다. 나는 풀고 나서 왜 맞았는지 잘 모르겠어서 구글링하다가 여기를 발견했는데 정리를 너무 잘 해놓으셨다. 코드 #include using namespace std; int dp[1003][1003]; int n, k; const int mod = 1e9 + 3; int dpf(int cur, int cnt) { int &ret = dp[cur][cnt]; //cnt가 1이면 남은 것중에 아무거나 하나만 칠하면 됨 if (cnt == 1) return cur; //cur이 2 * cnt보다 작으면 인접하는 경우가 무조건 한..

백준[17404] RGB거리 2

2021. 7. 4. 22:23 Algorithm/BOJ

풀이 이 문제는 RGB거리와 똑같이 dp문제지만 이 문제는 마지막 집과 1번 집이 연결되어 있다. 그렇기 때문에 첫 번째 집을 고정시켜 n번째에 첫 번째 색과 같은 경우를 배제시켜야 한다. dp[i][j] = i - 1에서 현재 색이 아닌 경우의 최소 + arr[i][j] (i : 현재 위치, j : 현재 색) 코드 #include #include using namespace std; int arr[1002][3]; int dp[1002][3]; int main() { int n; scanf("%d", &n); for (int i = 1; i

백준[2098] 외판원 순회

2021. 7. 3. 17:43 Algorithm/BOJ

문제 링크 http://icpc.me/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 TSP(Traveling saleperson)라고 불리는 웰노운 문제다. 비트마스크와 dp를 이용하여 문제를 풀 수 있다. dp 정의는 dp[n][state] = 1부터 시작하여 state에 있는 점을 모두 지나 n번 노드까지 올 때 필요한 최소 비용으로 할 수 있다. 어느 정점에서 시작하던 사이클을 돌기 때문에 시작 정점은 고려할 필요가 없다. 나는 마지막 노드에서 0번..

백준 [1311] 할 일 정하기 1

2021. 7. 3. 15:21 Algorithm/BOJ

풀이 dp[현재 사람][이전까지 수행한 일의 상태] = 현재 일의 상태까지의 최솟값 이 문제는 비트마스크와 dp를 이용하여 풀이할 수 있다. 이전까지 수행한 일의 상태를 0011 -> 1, 2번이 일을 한 상태와 같이 비트를 이용하여 상태를 표시한다. 코드 #include #include int d[22][22]; int dp[22][1 b ? b : a; } int dpf(int cur, int state) { int &ret = dp[cur][state]; //모든 일을 한 상황 ex) n = 3일때 1000 - 1 = 0111 if (state == (1

백준[2533] 사회망 서비스(SNS)

2021. 6. 24. 13:26 Algorithm/BOJ

풀이 방법 이 문제는 트리에서 dp를 이용하는 문제이다. dp[현재 노드][현재 노드가 얼리어답터인가 여부]로 dp테이블을 만들고 현재 노드가 얼리어답터가 아니라면 자식노드는 항상 얼리어답터이고, 얼리어답터라면 얼리어답터일수도, 아닐수도 있다. 이 문제는 이 문제 와 매우 비슷하여 쉽게 해결하였다. 코드 #include using namespace std; vector v, tree; int dp[1000006][2]; bool visited[1000006]; //단방향 그래프로 바꾼다 void dfs(int cur) { if (visited[cur]) return; visited[cur] = true; for (auto nxt : v[cur]) { if (!visited[nxt]) { tree[cur]..

백준[2213] 트리의 독립집합

2021. 6. 24. 11:31 Algorithm/BOJ

풀이 방법 이 문제는 트리에서의 dp문제 이다. 저는 맞왜틀을 외치다 여기 를 참고했습니다. 우선 dfs를 이용하여 임의의 루트를 정하여 그 트리의 경로를 저장합니다. dp정의는 dp[현재 노드][현재 노드를 포함하는가 여부]로 정의하고, 만약 현재 노드를 포함한다면 자식 노드는 포함 할 수 없고, 포함하지 않는다면 자식노드를 포함하든 안하든 상관이 없다. 포함하는 경로 추적은 루트 노드부터 시작해서 dfs를 돌며 dpf를 돌때 저장한 배열의 값이 true인 경우를 ans배열에 저장한다. 코드 #include #include #include using namespace std; int cost[10004], dp[10004][2], check[10004], res; vector v, tree; vecto..

티스토리툴바