정화 코딩

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 | 2..

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는 짝수)즉, 짝수 내에서와 홀수 내에서의 축의 배치 ..

https://www.acmicpc.net/problem/11054 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(n); for (int i = 0; i > a[i]; vector dp1(n); vector dp2(n); for (int i = 0; i a[j]) maxt = max(maxt, dp1[j]); } dp1[i] = maxt + 1; } for (int i = n - 1; i >= 0; i--) { in..

9회차 - dp  피보나치 수 2https://www.acmicpc.net/problem/2748피보나치 수를 구하는 걸 재귀로 구현하게 되면 시간 복잡도가 O(2^n)이므로 n이 조금만 커져도 실행 시간이 기하급수적으로 늘어나게 됩니다. 이는 같은 피보나치 값을 여러 번 중복 계산하기 때문입니다. 예를 들어, fib(5)를 계산할 때 fib(3)이 두 번, fib(2)가 세 번 호출되는 식으로 불필요한 연산이 계속 발생합니다.따라서 중복 계산을 막기 위해 이전에 계산한 값들을 저장하고 활용해야 합니다. 이럴 때 사용하는 대표적인 방법이 동적 계획법(DP)를 사용하게 되는 것입니다.#include #include using namespace std;int main() { ios_base::sync_..

https://www.acmicpc.net/problem/11048 #include #include #include using namespace std;int dx[3] = {1, 0, 1};int dy[3] = {0, 1, 1};vector> a;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; a = vector>(n, vector(m)); for (int i = 0; i > a[i][j]; } } queue> q; q.push({0, 0, a[0][0]}); int ans = 0; while (!q.empty..

https://www.acmicpc.net/problem/2096 #include #include using namespace std;int const INTMAX = 1000000000;int const MAX_N = 100000;int m[MAX_N][3];int dpmax[2][3];int dpmin[2][3];int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i > m[i][j]; } } for (int j = 0; j 처음에는 dp 배열을 n * 3으로 선언했었는데 메모리 초과가 났었다. (MLE) 생각해보니 d..