본문 바로가기

분류 전체보기721

[백준 11689] GCD(n, k) = 1 [C] 풀이 Euclidean algorithm을 사용해 풀이할 수 있지만, 최대 10^12의 수들에 대해 계산을 해야하므로 시간제한에 걸린다. Euler product formula을 사용해 쉽게 풀이할 수 있다. 나누어 떨어지는 소인수(p)를 찾아 Euler product formula에 적용시키면 된다. p-1 / p (= 1- 1/p)를 n에 곱해주어야 한다. p로 먼저 나눈 후 p-1을 곱해주자. for (long long p = 2; p*p 2021. 8. 11.
[백준 17626] Four Squares [C] 풀이 단순히 가장 큰 제곱수로 수를 구성하는 방법은 최소 제곱수의 개수의 만족이 성립하지 않는다. 때문에, 입력받은 n까지 모든 수에 대해 계산을 해봐야 한다. Square Free Integer같은 경우 이전의 수를 구성하는 제곱수의 개수 + 1을 만족하며 이러한 수의 밀집도는 리만 가설이 참이라는 전제하에 약 61%이다. ("백준 1557, 제곱 ㄴㄴ" 중 "Mobius function의 반환값의 개수 추측") 따라서 다음과 규칙을 기본으로 사용했다. for (int i = 1; i = 4 일 때는 Square Free Integer가 아닌 수들도 존재하며, 처음에 언급했듯이 가장 큰 제곱수의 구성이 최소 제곱수의 개수를 만족하지 않으므로, 구성 가능한 제곱수들 중 최소 제곱수의 개수를 찾아야 한다... 2021. 8. 11.
[백준 15657] N과 M (8) [C] 풀이 "백준 15652, N과 M (4)"를 참고해 풀이했다. 기존에는 1부터 입력받은 N까지의 수들 중에서 수열을 생성해야 했다. 이번에는 N개의 수를 이용해 수열을 생성하면 된다. 소스코드 #include #include int arr[8], N, M, num[8]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0; i num[i]) break; if (j == depth) arr[depth].. 2021. 8. 10.
[백준 15654] N과 M (5) [C] 풀이 "백준 15649, N과 M (1)"을 참고해서 풀이했다. 기존에는 1부터 입력받은 N까지의 수들 중에서 수열을 생성해야 했다. 이번에는 N개의 수를 이용해 수열을 생성하면 된다. 소스코드 #include #include int arr[8], N, M, num[8]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0; i < N; i++){ if (!depth) arr[0] = num[i]; else{ int j; for (j = 0; j < depth; j++) if (arr[j] == num[i]) break; if (j == depth) arr[dept.. 2021. 8. 10.
[백준 15652] N과 M (4) [C] 풀이 "백준 15650, N과 M (2)"를 참고해서 풀이했다. 기존의 코드에 같은 수를 여러번 고를 수 있도록 수정만 하면 된다. for (j = 0; j i) break; // arr[j]에 담긴 수보다 작은 경우에만 저장하지 않는다. 소스코드 #include int arr[8], N, M; void BT(int depth){ for (int i = 1; i i) break; if (j == depth) arr[depth] = i; else continue; } if (depth + 1 == M){ for (int idx = 0; idx < M; idx++) printf("%d ", arr[idx]); putchar(10); }else BT(depth .. 2021. 8. 10.
[백준 1788] 피보나치 수의 확장 [C] 풀이 F(1) = 1 = F(0) + F(-1), F(-1) = 1 F(0) = 0 = F(-1) + F(-2), F(-2) = -1 F(-1) = 1 = F(-2) + F(-3), F(-3) = 2 F(-2) = -1 = F(-3) + F(-4), F(-4) = -3 F(-3) = 2 = F(-4) + F(-5), F(-5) = 5 n이 음수이고, 짝수일때만, F(n)이 -1이다. 소스코드 #include int main(){ int n, op = 1; long long dp[2] = {0, 1}; scanf("%d", &n); if (n = 2){ for (int i = 1; i.. 2021. 8. 10.

티스토리툴바