정화 코딩

https://www.acmicpc.net/problem/1509 dp 배열 2개를 사용해서 풀었다.1. 모든 구간에 대해서 팰린드롬인지 아닌지를 저장하는 배열p[i][j] : i부터 j까지의 문자열이 팰린드롬이면 true, 아니면 false이 배열을 채울 때는 구간의 길이가 1일 때, 2일 때, ... 순서로 채워준다. 어떤 구간이 팰린드롬이고 직전 문자와 직후 문자가 같으면 그 구간도 팰린드롬임을 활용해서 채우면 된다.2. 팰린드롬 분할 개수의 최솟값을 저장하는 배열 (정답을 구하는 배열)dp[i] : i까지의 문자열의 팰린드롬 분할 개수의 최솟값이 배열은 0부터 j까지의 팰린드롬 분할 개수의 최솟값, 즉 dp[j]가 x이고 j+1부터 i까지의 문자열이 팰린드롬이면 dp[i]를 x + 1로 갱신할 수..

https://www.acmicpc.net/problem/1106 Knapsack 문제 중에서도 Unbounded Knapsack 문제이다.Unbounded Knapsack 문제는 Knapsack 문제 중 아이템을 무한히 선택 가능한 상황이다. 사실 Unbounded Knapsack 문제는 처음이라서, 나는 처음에 아이템을 복사해주고 일반적인 Knapsack처럼 하면 되는 줄 알았다. (찾아보니 이건 아이템을 정해진 횟수만큼만 선택할 수 있는 Bounded Knapsack 문제에서 사용할 수 있는 방법인 것 같다.)첫 번째 풀이: 홍보 도시를 중복으로 사용할 수 있도록 복제 + 2차원 dp 배열을 사용해서 냅색#include #include using namespace std;int MAX_COST = ..

https://www.acmicpc.net/problem/1005 게임 개발과 완전 비슷한 문제이다.이 문제에 대한 설명과 풀이는 이 글에 있다. #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int n, k, w; cin >> n >> k; vector> g(n + 1); vector time(n + 1); vector totaltime(n + 1); vector indegree(n +..

https://www.acmicpc.net/problem/7579 0-1 냅색 문제이다. 기본적인 0-1 냅색에 대한 내용은 이 글의 평범한 배낭 문제 부분에 잘 정리되어 있다. 기본적인 0-1 냅색에서의 dp 배열은 다음과 같다.dp[i][j] : 가방의 무게가 i이고, j번째 물건까지 살펴봤을 때, 가방에 담을 수 있는 최대 가치 그래서 다시 이 문제로 돌아오면... 이 문제는 크게 두 가지 방법으로 해결할 수 있다.1. 2차원 dp 배열로 해결하기dp[i][j] : i만큼의 비용으로 j번째 앱까지 확인했을 때, 얻을 수 있는 최대 메모리#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.t..

https://www.acmicpc.net/problem/1562 10844번 쉬운 계단 수 문제의 어려운 버전인가 보다. 그 문제에 대한 풀이는 이 글에 있다. 쉬운 계단 수와의 다른 점은 0부터 9까지의 수가 모두 등장해야 한다는 것이다. 그러면 어떤 어떤 수를 사용했는지 비트마스킹으로 표시해주면 되겠네! dp[i][j][k]: 길이가 i이면서 j로 끝나는데, 현재까지 사용한 수가 k 상태인 계단 수의 개수(0을 사용했으면 2^0으로, 1을 사용했으면 2^1으로... 표현하고 그걸 모두 합한 값을 k로 사용한다. 즉 k는 0 이상 1023 이하의 값이다.)0으로 끝나는 수 → dp[i][0][k | 2^0] += dp[i - 1][1][k]9로 끝나는 수 → dp[i][j] = dp[i][9][k |..

https://www.acmicpc.net/problem/10844 dp[i][j] : 길이가 i이면서 j로 끝나는 계단 수의 개수0으로 끝나는 수 → dp[i][0] = dp[i - 1][1]9로 끝나는 수 → dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]나머지로 끝나는 수 → dp[i][0] = dp[i - 1][1] #include #include using namespace std;int mod = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector> dp(n + 1, vector(10, 0)); ..

https://www.acmicpc.net/problem/17070 그냥 bfs 해주되, 파이프가 놓여 있는 방향까지 큐에 넣도록 했다. 그래서 현 상태를 기준으로 어떻게 움직일 수 있는지를 체크해서 (n, n)에 도달하면 한번 카운트 해주는 식으로 구혔했다.어차피 움직이는 방향이 무조건 오른쪽 또는 아래이기 때문에 시간 안에 해결 가능하다고 생각했는데, 제출해보니 좀 간당간당하고 dp로 풀어야 했던 문제인 듯하다. #include #include #include using namespace std;// 파이프가 놓여 있는 방향 {가로, 세로, 대각선}int px[] = {0, -1, -1};int py[] = {-1, 0, -1};vector>> d = { {{0, 1, 0}, {1, 1, 2}..

https://www.acmicpc.net/problem/30788 각도가 d인 축을 기준으로 대칭이동 시켰을 때 그림이 얼마나 회전하는지를 계산하기 위한 뻘짓...그래서 식은 nxt = (2 * d - cur) % 360 이다.(cur: 대칭이동 전의 그림의 각도, nxt: 대칭이동 후의 그림의 각도, d: 대칭이동 축의 각도) 이건 식 정리 과정...그래서 정리하면 다음과 같다. 우선 그림이 원래 상태로 돌아오려면 대칭이동은 짝수번 시켜야 한다.축이 홀수개이면 무조건 불가능하므로 생각해주지 않아도 된다. k번의 대칭이동 후의 그림의 각도는 2 * d(k) - 2 * d(k-1) + ... + 2 * d(2) - 2 * d(1) 가 된다. (k는 짝수)즉, 짝수 내에서와 홀수 내에서의 축의 배치 ..