[BOJ] 백준_1748번_수 이어 쓰기1 / C언어, C++백준 알고리즘2021. 9. 15. 11:30
목차
문제 출처
https://www.acmicpc.net/problem/1748
문제
1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.
출력
첫째 줄에 새로운 수의 자릿수를 출력한다.
실패한 코드
//[BOJ] 1748번_수 이어 쓰기1_실패한 코드
#include <iostream>
using namespace std;
int main()
{
int count = 0;
int n; cin >> n;
for (int i = 1; i <= n; i++)
{
if (i < 10)
count++;
else if (i < 100)
count = count + 2;
else if (i < 1000)
count = count + 3;
else if (i < 10000)
count = count + 4;
else if (i < 100000)
count = count + 5;
else if (i < 1000000)
count = count + 6;
else if (i < 10000000)
count = count + 7;
else if (i < 100000000)
count = count + 8;
}
cout << count << endl;
}
메모리 초과 코드
//[BOJ] 1748번_수 이어 쓰기1_메모리 초과
#include <iostream>
#include <sstream>
using namespace std;
int main()
{
int n; cin >> n;
if (n < 1 || n>100000000)
{
cout << "n의 범위를 벗어났습니다." << endl;
exit(1);
}
string all;
for (int i = 1; i <= n; i++)
{
string s = to_string(i);
all.append(s);
}
cout << all.length() << endl;
return 0;
}
코드
//[BOJ] 1748번_수 이어 쓰기1
#include<iostream>
using namespace std;
int main() {
int n, r;
cin >> n;
for (int i = 1; i <= n; i *= 10)
r += n - i + 1;
cout << r << endl;
return 0;
}
쉬워보였는데 하다보니 요즘 푼 문제들 중에는 가장 어렵다고 느꼈다. 첫 실패한 코드는 무작정 1억 이내의 범위만 맞추고 작성한 코드이기 때문에 실패할 것을 어느 정도 짐작하고 있었다. 하지만 메모리 초과 오류는 처음 받아봐서 어떻게 고쳐야할지 감이 안잡혔다. n을 입력받은 후 1부터 n까지의 값을 각각 string s에 to_string()메소드를 이용해서 문자열로 바꾼 후 append()메소드를 이용해 문자열 all에 이어 붙인다. 반복문이 끝나면 all의 문자열 길이를 출력한다. 이 코드가 메모리 초과 판정을 받고 코드를 아예 다시 새롭게 짜야 했다. 찾아보니 해당 알고리즘에 규칙성이 있었고 1부터 입력받은 n값 까지 반복시키며 n에서 i를 빼고 1을 더한값을 계속 더해주면 자릿수가 구해진다.
728x90
반응형
LIST
'백준 알고리즘' 카테고리의 다른 글
[BOJ] 백준_17427번_약수의 합 2_C/C++ (0) | 2021.09.17 |
---|---|
[BOJ] 백준_1037번_약수 / C, C++ (0) | 2021.09.16 |
[BOJ] 백준_1476번_날짜 계산 / C++ (0) | 2021.09.14 |
[BOJ] 백준_2309번_일곱 난쟁이 / C++ (0) | 2021.09.13 |
[BOJ] 백준_10872번_팩토리얼 / C++ (0) | 2021.09.12 |
@kdj :: Childev'note
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!