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..
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]..
문제 : https://www.acmicpc.net/problem/15460 s[0...n-1]에 주어진 score를 저장합시다. 이 문제는 k를 1부터 n-2까지 증가시키며, s[k]...s[n-1] 중 최솟값을 제외한 것의 평균을 최대로 하는 k들을 구하는 문제입니다. 최대 n이 100,000이므로 O(n^2)이 되면 안되는데, 다음과 같이 O(n)에 score의 부분합과 부분최솟값을 미리 구해놓으면 나중에 s[k]...s[n-1] 중 최솟값을 제외한 것의 평균을 O(1)에 구할 수 있습니다. a[i] : s[n-1]부터 s[i]까지 합. m[i] : s[n-1]부터 s[i]까지 최솟값. 그 다음부터는 k를 1부터 n-2까지 증가시키며, a[k] - m[k] / (n - k - 1)이 최대가 되는 k..
문제 : https://www.acmicpc.net/problem/16771 barn 1에 있는 10개의 bucket 중 하나를 사용해 우유를 옮기고, barn 2에 있는 11개의 bucket(방금 barn 1에서 2로 옮기는 데 사용한 bucket 포함) 중 하나를 다시 barn 1으로 옮기는 작업을 한 세트로 생각합니다. 이 세트를 2번 실행하면 모든 경우의 수를 탐색할 수 있습니다. 시간복잡도: O(N^4) (N: bucket의 개수) #include #include using namespace std; int bucket1[10], bucket2[10]; bool check[1199]; // 802~1198 void back_and_forth(int barn1, int depth) { if(dep..