본문 바로가기
728x90

수학33

[C++] 백준 17427 약수의 합 2 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 해결 시간으로 보았을 때 $O(n)$의 시간복잡도를 가져야한다. 그러기 위해서는 각각의 약수의 합을 구해서 더하는 방식으로 할 수 없다.(최소 $O(n\sqrt{n})$) 1부터 n까지 반복문 $i$을 돌릴 때 n을 $i$로 나누면 n까지 숫자중 $i$를 약수로 갖는 개수가 나온다. 따라서 $i$를 곱해주면 $i$를 약수로 갖는 것들.. 2023. 10. 31.
[python] 백준 1201 NMK https://www.acmicpc.net/problem/1201 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 문제 해결 먼저 수열을 구할 수 있기 위한 n의 범위를 알아야한다. m+k-1 ≤ n ≤ m*k 이다. n이 가장 작을 때는 [1, 2, 3, .. . m, m-1, m-2, . . . m+k-1] 수열이며 n이 가장 클 때는 [k,k-1,k-2, . . . 1, 2*k, 2*k-1, . . . k+1, . . . m*k, m*k-1, . . . (m-1)*k + 1] 이다. n이 범위 안에 들어오면 처음으로 k개의 숫자를 내림차순해서 k개의 내림차순을 만든다. 이제 k+1~n까지 정렬해서 m-1개의 오름차순 수열을 만들어야한다. 여기서부터 너무.. 2023. 8. 27.
[python] 백준 5615 아파트 임대 https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 문제해결 2xy+x+y로 무엇을 할 수 있을지 생각하면 아무것도 할 수 없다.(1차 고비) 인수분해를 해야할 것 같은데 S = 2xy+x+y라 할 때 2S+1 = (2x+1)(2y+1)로 인수분해 할 수 있다. 2S+1은 두 홀 수의 곱으로 나타낼 수 있는 것이다. 그럼 이것을 왜 하는 것인가? 바로 2S+1이 소수인지 판별해서 S를 판별하면 되는 것이다. 2S+1이 소수인지 판별하는 것은 밀러-라빈 소수 .. 2023. 7. 31.
[python] 백준 1328 고층 빌딩 https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 문제 해결 dp를 써야겠다라는 생각이 드는데 어떻게 써야할지 고민이 되는 문제 n이 1이상 100이하이기 때문에 삼 중 반복문을 써도 괜찮다. dp[i][j][k]를 i개의 빌딩이 있을 때 왼쪽에서 보면 j개 오른쪽에서는 k개 보이는 배열가지수라고 하자. 그러면 dp[1][1][1] =1 이 된다. 가장 기본 값 i-1개의 빌딩이 배열되어있다고 하자. 이제 빌딩 하나를 더 세워 dp[i][j][k.. 2023. 5. 8.
728x90