N개의 side를 채우기 위해 작은 Polygon부터 생각해보면 polygon의 side 개수는 배수로 증가한다. 예를 들어, 33 = 3(1+10) 혹은 11(1+2)와 같이 나타낼 수 있다. 재귀적으로 3(1+10)은 또 3(1+2(1+4))와 같이 나타낼 수 있다. f(p)를 다음과 같이 정의하자. f(p) : p를 만들기 위해 2보다 크거나 같은 p의 약수 qi를 사용해서 p=q0+q0q1+q0q1q2+...+q0q1...qn으로 나타낼 때 최대 항의 수 말이 좀 어려운데, 예를 들어보면 22=2(1+10)=2(1+2(1+4))이므로 f(22)=3이다. g(p) : p를 만들기 위해 3보다 크거나 같은 p의 약수 qi를 사용해서 p=q0+q0q1+q0q1q2+...+q0q1...qn으로 나타낼 때..
문제: https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 � www.acmicpc.net 1. 주사위를 3번 던졌을 때 각 눈을 a, b, c라고 하고, 이 때 얻는 상금을 prize(a, b, c)라고 하자. 2. 최근에 던진 두 번의 주사위 눈을 a, b라고 하고, 남은 기회를 n이라고 하자. 이때, 상금의 기댓값을 f(a, b, n)라고 하자. 그러면 f(a, b, n)은 1 c) { return a * 100; } else if(b > c) { return b * 100..
마스터 정리를 사용하기 위해선 시간 복잡도 점화식이 다음과 같이 정의되어야 한다. $$T(n) = aT(n/b) + f(n)$$ 그리고 다음과 같이 세 가지 제약 조건이 있다. 1. $f(n)$은 다항식(polynomial function)이어야 한다. 단, $f(n)$이 다항식이 아니더라도 극명하게 적용될 수 있음을 증명하면 사용할 수 있다. ($n^2$ > $n log n$ 또는 $n^2$ 1$인 양의 실수여야 한다. 재귀를 호출할 때 그 호출 비용이 현재보다 작아야 한다는 것을 의미한다. 3. 정규 조건(regularity condition) ${af(n/b)} \leq {cf(n)}$을 만족하는 $c < 1$가 존재해야 한다..
https://www.acmicpc.net/problem/16361 16361번: LED Your program is to read from standard input. The input starts with a line containing an integer n (1 ≤ n ≤ 300,000), where n is the number of tuples (vi, li) in the experimental data. In the following n lines, each line contains two integers, which range i www.acmicpc.net 이 문제는 2018 ACM-ICPC Seoul Regional E번 문제다. 실험에서 나오는 l 값들은 정수이므로 error의 단위는 ..
어떤 구간이 다른 구간을 포함하고 있을 때, 포함되는 구간을 제거하면 최대가 된다. 그렇지 않을 경우, 모든 구간이 커버하는 영역의 총 길이를 A라고 하고, 어떤 두 구간도 overlap 되지 않는 가장 짧은 영역의 길이를 B라고 하면, A-B가 답이 된다. 왼쪽부터 sweeping 하면서 A와 B를 구하면 O(N)이고, 정렬이 O(NlogN)이므로 총 시간복잡도는 O(NlogN)이 된다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false), cin.tie(NULL); int N; vector se, shift; cin >> N; for (int i = 0; i < N; i++) { int star..
t[i] : i번 타일에 도착할 수 있으면 true, 없으면 false. 부츠를 1번부터 순서대로 신어보면서 t[i]를 채워가면 된다. for 1 B; for (int i = 1; i > f[i]; for (int j = 1; j > s[j] >> d[j]; bool t[251] = {false, true,}; // t[1] = true; int j; for (j = 1; j = f[i - k]) { // If he can wear boots j on tile i-k. able = true; break; } } t[i] |= able; } } if (t[N]) break; } cout
문제 : https://www.acmicpc.net/problem/15462 크기가 2 이상인 SCC 내 원소의 개수와 크기가 1이고 자기 자신을 가리키는 SCC 개수를 더해서 출력하면 된다. SCC 찾기는 Tarjan's algorithm을 사용하였다. #include #include #include #define MAX_N 100000 using namespace std; int dfsn[MAX_N + 1], scc[MAX_N + 1], r, c; vector vt[MAX_N + 1]; vector res; stack st; int dfs(int here) { dfsn[here] = ++c; int ret = dfsn[here]; st.push(here); for (int next : vt[here]..