그냥 하는 노트와 메모장

A. B. 걷다보니 신천역 삼 (Small)/(Large) 단순 dynamic으로 생각할 수 있다. 마지막 수에 대해서 0,1,2가 들어갈 수 있으므로 현재 k자리 수에 대해서 3*dp[k]를 처리해주면 된다. 단 int의 경우 3개를 더했을 경우 오버플로가 발생할 수 있으니 유의. #include #define MOD 1000000009 int main() { long long N,R=0; scanf("%lld", &N); if (N > 1) R = 2; while (N-- > 2) R = ((R + R) % MOD + R) % MOD; printf("%lld", R); return 0; } C. 나는 행복합니다 ~ 규칙이 있는 2차원에서 해싱을 할 수 있는지 물어보는 문제. 가로로 순서대로 적혀지기 ..

A. Eleven 주어진 길이에 대해 피보나치 수가 넘어가지 않을 때까지 'O'로 바꿔주기만 하면 된다. #include #include int main() { int N,a=1,b=1,t; char name[1001] = {}; scanf("%d", &N); memset(name, 'o', N); name[0] = 'O'; while (a + b

A. Perfect Squares sqrt 함수를 이용하여 제곱수인지 확인하고 그 중에서 최대값을 찾으면 된다. #include #include int max_v(int a, int b) { return a > b ? a : b; } int main() { int n, D,ans=-1e9; double tD; scanf("%d", &n); while(n--) { scanf("%d", &D); if (D >= 0) { tD = sqrt(D); if (tD != (int)tD) ans = max_v(ans, D); } else ans = max_v(ans, D); } printf("%d", ans); return 0; } B. Conan and Agasa play a Card Game Greedy하게 접근한..

조금 짜증나는 백트랙킹 문제였다. unsigned long long 범위를 벗어나지 않기 위해서는 곱셈과정을 직접 구현해야 한다. 그렇지 않으면 10자리 수에 대한 세제곱 수를 구할 때, 무조건 overflow가 발생한다. 기본 아이디어는 다음과 같다. 일의 자리에 대해서 생각을 해보자. 어떤 한자리 수 세제곱을 하면 숫자 k(0

A. 순서쌍의 곱의 합 단순 for 두번 O(N^2)으로는 시간초과가 나버린다. 구하는 것은 (A1*A2 + A1*A3 + ... + A1*AN) + (A2*A3 + A2*A4 + ... A2*AN) + ... + (AN-1*AN) 꼴이 된다. 규칙성을 말하자면 A1의 경우 A2부터 AN까지의 합에 곱셈을 해야하고, AK의 경우(1

A. 비밀번호 재귀 완전탐색을 구현한다. 모든 가능한 숫자에 대해서 사용했으면 1을 추가해준다. 매우 간단. #include int ans,n,m, used[10], mc[10]; void back(int p) { if (p >= n + 1) { bool f = 1; for (int i = 0; i < m && f; i++) if (!used[mc[i]]) f = 0; ans += f; return; } for (int i = 0; i < 10; i++) { used[i]++; back(p + 1); used[i]--; } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) scanf("%d", &mc[i]); back(1); printf..

그래프 이론 + dp 문제의 다소 신기한 문제라 포스팅한다. i가 3이상인 구간에 대해서 아래의 공식이 성립한다. 아래 그림을 보자. 먼저 dp[i-1]을 설명한다. i이지만 i->k가 아닌 경우 > 0 k로 가는 경우는 없이 세는 것이다. i이고 i->k인 경우 > 마찬가지로 k의 후보는 0~i-1이므로 총 i개, k에 대해 i를 연결하고 i에 대해 k를 연결하면 나머지 i-2개에 대해 재배정이 되지 않도록 하는 방법의 수는 dp[i-2]가 된다. 따라서 i*dp[i-2]가 된다. 이 이후로 사이클 3개, 4개에 대해서 다루지 않는 이유는 이미 dp[i-1]에 포함되어 있기 때문이다. k가 i를 가리키고 있는 와중에 나머지 i-1개의 정점들 간의 재배정되지 않는 경우 안에 이 것이 포..