[백준] 1748-수 이어 쓰기 1(C++)

문제링크:https://www.acmicpc.net/problem/1748

1748번: 수 이어 쓰기 1

 

전형적인 구현문제입니다. 

다만 n이 최대 1억번까지이기에 구현방법에 대해서 조금 생각해봐야했습니다.

 

저는 그냥 일반적인 논리로 접근했습니다.

#include <iostream>
using namespace std;
int n = 0, result = 0;

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		if (i <= 9)
			result += 1;
		else if (i <= 99)
			result += 2;
		else if (i <= 999)
			result += 3;
		else if (i <= 9999)
			result += 4;
		else if (i <= 99999)
			result += 5;
		else if (i <= 999999)
			result += 6;
		else if (i <= 9999999)
			result += 7;
		else if (i <= 99999999)
			result += 8;
		else
			result += 9;
	}
	cout << result << endl;
}

 

네 당연히 ac입니다.

 

하지만 조금 더 효율적인 코드를 찾아봤습니다.

 

#include<cstdio>
int n, r;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i *= 10) 
		r += n - i + 1;
    printf("%d", r);
    return 0;
}

크으 ... 아름다운 코드...

 

위 코드의 핵심은 매번 반복문마다 1의자리수의 합을 더해주고, 다음 반복문에서는 2의 자리수의 합을 더해준다는 개념입니다. 

대략 120정도의 값을 대입해보시면 이해가 가실겁니다.

 

 

이렇게 구현문제는 풀어보는 것이 끝이 아니라 다른사람의 효율적인 코드를 보는게 더욱 도움이 된다고 생각합니다.

 

화이팅 :)