본문 바로가기
반응형

수학35

[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.
[Python] 백준 #1684 같은 나머지(정수론) 이번 문제는 주어진 숫자들에 대해서 나머지가 같은 수가 되는 나눔수 중 최대의 정수를 찾는 것입니다. 나머지가 같다는 것은, 숫자들의 차이에 대한 최대공약수를 구하는 것과 같습니다. \[ Find~ maximum~ such~ D~ that~ \forall i ~ a_i ~mod ~D = k \Longleftrightarrow gcd( a_i - min(a) ) \] 음수를 피하기 위해서 주어진 수 중에 가장 작은 수를 찾습니다. 그리고 나머지 수 중에 가장 작은 수와 같은 경우를 제외하고, 그 차이를 기록합니다. 마지막으로 그 차이들의 수열의 최대 공약수를 구합니다. 다음은 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. """ baekjoon #1684 - by Aubrey Choi - creat.. 2022. 9. 29.
728x90

티스토리툴바