본문 바로가기

수학44

[C/C++] 백준 #1789 수열의 합(수학) 서로 다른 수들로 이루어진 수열의 합을 원하는 값으로 맞추는 방법은 아주 다양하게 있을겁니다. 그런데, 참여하는 수의 갯수를 최대한으로 하기 위해서는 참여하는 수가 작을 수록 좋겠죠. 이 문제를 풀기 위해서는 바로 이 방법을 사용했습니다. \[ N(N+1)/2 \le S \] 위의 식을 만족하는 최대의 N을 구하면 되겠죠. 근의 공식을 이용하면 쉽게 N의 범위를 구할 수 있습니다. \[ N \le \frac{1 + \sqrt{1+8S}}{2} \] 오른쪽항은 정수일수도 아닐 수도 있지만, N은 정수여야 하므로, 오른쪽항의 값의 정수값을 구하면 됩니다. 다음은 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //--------------------------------------------------.. 2022. 10. 22.
[C/C++] 백준 #1748 수 이어 쓰기 1(수학) 수 이어 쓰기 문제는 N이 주어지면 1부터 N까지의 숫자를 그대로 이어썼을 때 몇자리 숫자가 될 것인지를 물어봅니다. 무한대의 수를 소수로 만들면, 이 수는 초월수가 된다는 것이 증명되었는데, 비슷한 개념이지만, 여기는 유한개의 수를 붙여 쓰는 것이고, 자릿수만 계산하면 되는 문제라 어려운 수학이라고 보기는 힘듭니다. 한자리 숫자는 9개가 있고, 두자리 숫자는 90개가 있고, 세자리 숫자는 900개가 있습니다. k자리숫자는 \( 9 \times 10^{k-1} \)개가 있게 됩니다. 이를 이용하면 이 문제를 쉽게 풀 수 있습니다. 예를 들어서 372까지의 숫자를 쓴다고 해보죠. 1) 9보다 큰 수이므로 9자리가 나옵니다. 2) 9를 빼면, 363이 되고 이 수는 90보다 크므로, 189가 됩니다. 3) .. 2022. 10. 9.
[C/C++] 백준 #1747 소수&팰린드롬(수학) 이번 문제는 n 이상의 수중에 가장 작은 소수이면서 팰린드롬이 되는 수를 찾는 문제입니다. 구현을 위한 핵심은 다음과 같습니다. 1) n의 앞부분 절반의 수를 구합니다. 예를 들어서 120의 경우라면 3자리 숫자에 12가 됩니다. 31과 같은 숫자는 2자리 수에 3이 됩니다. 2) 절반의 수를 이용해서 같은 자리수의 팰린드롬을 구합니다. 120의 경우에는 121이 팰린드롬 수가 됩니다. 31의 경우에는 33이 팰린드롬이 됩니다. 이 수가 n 이상의 수가 된다면, 통과이고, 그렇지 않다면 절반의 수에 1을 더합니다. 이 수는 반드시 n보다 큰 수가 되기 때문에 1을 더하는 것으로 충분합니다. 3) 그 수부터 시작해서 팰린드롬이 되는 수 중에 소수인 수를 찾습니다. 여기서 사실 알고리즘 효율을 위해서 맨 첫.. 2022. 10. 9.
[C/C++] 백준 #1740 거듭제곱(수학) 이번문제는 3진수를 생각하면 됩니다. 단지 0과 1로만 이루어진 3진수가 되는 것이죠. 예를 들어서 5번째로 작은 거듭제곱수는 5가 이진수로 101이므로 \[ 101_{(3)} = 3^2 + 3^0 = 10 \] 이 됩니다. 마찬가지로 10은 \(1010_{(2)}\) 이므로 \[ 1010_{(3)} = 3^3 + 3^1 = 30 \] 이 됩니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------ // baekjoon #1740 // - by Edan // - created at 2019-07-02 //------------------------------------------------ #include // .. 2022. 10. 6.
[C/C++] 백준 #1735 분수 합(수학) 이번 문제는 간단하게 분수의 합을 구하는 식을 알면 풀 수 있습니다. 기약분수라고 한다면, 다음과 같이 표현할 수 있습니다. \[ \frac{a}{b} = \frac{a/g}{b/g} ~when~g = gcd(a, b) \] 두 분수의 합은 \(g = gcd(a, b)\)라고 할 때, \[ \frac{n}{a} + \frac{m}{b} = \frac{nb/g + ma/g}{ab/g} \] 기본적으로 이것들을 알면 이 문제를 풀 수 있습니다. 다음은 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------------------------------------------ // baekjoon #1735 // - by Aubrey C.. 2022. 10. 6.
[C/C++] 백준 #1722 순열의 순서(수학) 이번 문제는 순열의 순서를 아는 것입니다. 순열 경우의 수는 N이 주어지면, \(N!\)로 아주 큰 수가 됩니다. 순열의 경우의 수가 팩토리얼이라는 것은 아주 중요합니다. 우리가 10진수를 생각한다면, N자리의 숫자는 \(10^N\)개의 경우의 수를 가집니다. 이를 이용하면, 우리가 주어진 수가 몇번째 10진수인지 아주 쉽게 구할 수 있습니다. 팩토리얼로 이루어진 수도 마찬가지라고 생각하면 됩니다. N이 4라면 만들 수 있는 순열 수는 24가지가 됩니다. 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 432.. 2022. 10. 4.

티스토리툴바