목록Algorithm (121)
블로그 옮겼습니다
1 T; for(int t = 1; t > P; ll S = 1e12; ll GCD = gcd(P*S, S); ll C = S/GCD; S = P * C; S -= C; ans[4] = S/4; if(S%4) ans[S%4]++; ans[0] = C - ans[1] - ans[2] - ans[3] - ans[4]; cout
예를 들어 소수 0.375 를 정수로 만들어 주기 위하여 곱해야 하는 최소 정수는 몇일까?답은 40이 나와야 한다.10의 거듭제곱꼴인 매우 큰 수 S가 있다고 하자. 그리고 주어진 소수를 p라고 해보자.그러면 p*S 는 정수가 될 것이 분명하다. (물론 가장 낮은 소수점 자릿수보다 10의 지수가 크거나 같아야만 한다)그렇다면 gcd(pS, S) 를 해보자. 만약 p가 정수였다면 gcd(pS, S)는 S임이 자명하다. 하지만 p 가 소수이기때문에p를 정수로 만들어 주기 위한 S의 최소 약수만큼이 빠질것이다. 그렇다면 p를 정수로 만들어 주기 위한 S의 최소 약수는 S/gcd(pS, S) 가 될 것이다. 그런데 잘 생각해 보면어떤 소수를 분수의 합꼴로 나타내보면, 즉 3*(1/10^(-1)) + 7*(1/1..
개인적으로 가장 알아야한다고 생각하는 네가지를 쓰겠다. 1번째\(\binom n k = \binom {n-1}{k} + \binom {n-1}{k-1}\) 예를 들어 생각해보면 쉬운데 어떤 반에서 n명의 학생중 k명의 대표를 뽑으려고하는데 이 때의 경우의 수는특정 학생 x 에 대해 두가지의 케이스로 나누어 생각해 볼 수가있다.학생 x를 뽑는 경우와 뽑지 않는 경우 이렇게 두 가지의 케이스이다.만약 학생 x를 뽑는다면 나머지 n-1 명의 학생들 중에 k-1명의 대표를 더 뽑아야 하므로 \(\binom {n-1}{k-1}\) 가지의경우의 수가 있으며, 학생 x를 뽑지 않는다면 나머지 n-1 명의 학생들 중에 k명의 대표를 뽑아야 하므로\(\binom {n-1}{k}\) 가지의 경우의 수가 있다. 그래서 두 ..
문제 링크 \(1\leq{a,b,c}\leq{10^9}\) 일 때, A * B = C 를 만족하면서 |A-a| + |B-b| + |C-c| 가 최소가 되게 하는 자연수 A,B,C 에 대하여|A-a| + |B-b| + |C-c| 를 구하는 문제이다. 처음에 삼분탐색 등으로 구하려 했는데 풀리지 않았다. 애초에 삼분탐색만으로는 풀 수 없는 문제같다.우선 가장 중요한 것 중 한가지는 A가 정해지면 |A-a| + |B-b| + |C-c| 가 최소값이 되기 위한 B와 C는자동으로 결정 된다는 것이다. 그 이유는우선 우리는 A가 이미 정해졌기 때문에 |A-a| + |B-b| + |C-c|를 최소로 만들기 위해서는 최대한B를 b와 같게 만들고 C를 c와 같게 만들어야 한다. 그런데 C는 A와 B의 곱으로 이루어 지기..
처음엔1234567ans = 0; map mp; if(mp[어떤답] == 0) mp[어떤 답] = 1, ans++; Colored by Color Scriptercs이렇게 했었는데 굳이 이렇게 할 필요없이 그냥 set에 넣고나서 마지막에 set.size() 를 하면 쉽게알수있다..
1번째 방법12345678stringstream ss1(S);for(string str1; getline(ss1,str1,' ');){ stringstream ss2(str1); vector in; for(string str2; getline(ss2,str2,',');) in.push_back(stoi(str2)); int a,b,c; tie(a,b,c) = {in[0],in[1],in[2]};}Colored by Color Scriptercs 2번쨰 방법1234567// "a,b,c d,e,f h,i,j" 와 같은 형태의 문자열 파싱하기 stringstream ss1(S);for(string str1; getline(ss1,str1,' ');){ int a,b,c; sscanf(str1.c_str(),..
문제 링크 \(1\leq{N}\leq{30}\)\(0\leq{M}\leq{30}\)\(1\leq{K}\leq{8}\) 이 문제는 N개의 집이있을 때 집과 집을 잇는 M개의 양방향 도로를 설치 하는 문제이다.A번 집과 B번 집을 잇는 도로를 설치하기 위해서는 01); } ll& cache = dp[u][v][k][mask]; if(cache != -1) return cache; cache = 0; cache = (cache + go(u,v+1,k,mask)) % mod; int nextmask = mask^(1
문제 링크 \(2\leq{N}\leq{10^5}\)\(1\leq{K}\leq{200}\) 이 문제는 N개의 노드로 이루어진 트리가 주어진다. 각 노드에는 가중치가 있다.K가 주어지는데 최대 K번 가지를 칠 수 있다는 것이다. 어떤 노드 u를 가지친다는 말의 정의는노드 u를 루트로 하는 서브트리를 제거한다는 것이다. 최대 K번 가지를 쳐서 남아있는 트리의 모든 노드의가중치의 합을 최대로 하고싶을때 이 최대 가중치합을 구하는 문제이다. 우선 처음에 일반적인 트리dp 문제처럼 이렇게 풀어 보려고했었다.dp[u][v][k] : 현재 노드 u를 보고있고 v개의 자식을 이미 봐주었으며 앞으로 최대 k번 가지칠수있을 때 최대 가중치 합 이렇게 하면 부분문제의 수는 최대 N*K 개이다. 왜냐하면 (u,v) 의 쌍은 간..
문제 링크 이 문제는 N개의 물통이 있고 L리터의 물을 N개의 각 물통에 나눠서 채우려고 하는데,물통에는 상한과 하한이 있어서 각 물통에 채울 수 있는 물의 양은 이 상한과 하한 사이의 양이어야만 한다. 이 때 N개의 물통에 채운 물의 양 중에서 가장 많은 양과 가장 적은 양의 차이가 최소가 되도록 하고싶다.이 떄의 차이를 구하는 문제이다. 단, 들어오는 입력들은 항상 L리터를 상, 하한에 맞춰 분배할 수 있는 방법이적어도 하나는 있다고 가정한다. 일단 이 문제는 두가지의 풀이가 있다.첫번째 풀이는 라인 스위핑(+그리디)이다. 내가 대회 때 푼 방법이 이 라인 스위핑인데대회가 끝나고 보니 나 말고는 라인스위핑으로 푼사람을 찾을 수가 없었다.좋은건지 안좋은건지.. 사실 처음에 다른 풀이 방법을 떠올렸다가 ..
문제 링크 격자의 사이즈 N,M 이 주어진다. 각 판은 '.' 또는 '1'~'9' 의 숫자이다. 그리고 n,m 이 주어지는데 n,m이란 어떠한 격자칸에서부터 시작하는 연속된 칸에 있는 수들의 합이 홀수가되어야 한다는 제약 조건에 대한 변수이다. 칸에서 아래로 n칸의 합은 홀수여야하고,오른쪽으로 m칸의 합도 홀수여야한다는 것이다. 물론 열 인덱스가 M-m+1 인 칸 까지만 적용되며행 인덱스가 N-n+1 인 칸까지만 적용된다. 이 때 '.' 인 칸에 적절한 '1'~'9'의 수를 넣어주어 위에서 말한 조건을 만족하도록 하는 방법의 수를 구하는 문제이다.일단 각 수가 홀수인지 짝수인지만 중요하기 때문에 현재 적혀있는 수가 실제로 몇이던 상관없고 짝수인지 홀수인지만중요하기 때문에 먼저 짝수는 0, 홀수는 1이라고..