본문 바로가기

Programming456

[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++] 백준 #1744 수 묶기(탐욕 알고리즘) 이 문제는 탐욕 알고리즘으로 풀기에 괜찮은 문제입니다. 수열이 주어지면 그 수를 다른 수와 묶어서 곱한 후 더하거나 수 자체를 더하는 방법을 사용합니다. 한번 사용된 수는 다시 사용될 수 없습니다. 그리고 모든 수가 참여되어야 합니다. 이렇게 했을 때 최대의 합을 구하는 것이 문제입니다. 예를 들어서 ( 3, -2, 5, -7, 0 ) 이 있다고 한다면, (-2 * -7) + (3 * 5) + 0을 하면 가장 최대수를 얻게 됩니다. 원리는 간단합니다. 0 이하의 수와 1보다 큰 수들, 그리고 1의 갯수를 구합니다. \(1a = a\)이므로 1은 곱하기보다는 자기 자신으로 더하는 것이 더 큰 수가 됩니다. ( 2, 3, 5, 7 ) 이렇게 4개의 수가 있다면, 가장 큰 값을 얻기 위해서는 큰수끼리 곱해나가.. 2022. 10. 8.
[C/C++] 백준 #1743 음식물 피하기(너비우선탐색) 이번 문제는 섬의 개수 구하기라든지, 섬의 넓이 구하기 문제와 비슷한 유형으로 너비 우선 탐색(BFS)나 깊이 우선 탐색(DFS)를 이용해서 푸시면 됩니다. 구현 자체는 깊이 우선 탐색이 더 쉽습니다. 너비 우선 탐색은 일단 큐를 사용해야 하기때문에 구현이 조금 더 까다롭다고 볼 수 있습니다. 그에 비해서 깊이 우선 탐색을 이용하면 재귀함수만 이용하면 되죠. 구현도 훨씬 간단하고요. 제가 작성한 소스입니다. 소스는 참고로 봐주세요. //-------------------------------------------------------------------- // baekjoon #1743 - Avoid The Lakes // - by Aubrey Choi // - created at 2019-08-06 .. 2022. 10. 6.
[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.
728x90

티스토리툴바