[Java] 수 이어 쓰기 1 [1748번]

https://www.acmicpc.net/problem/1748

• 예제 입력1

5

• 예제 출력1

5

• 예제 입력2

15

• 예제 출력2

21

• 예제 입력3

120

• 예제 출력3

252

---

• 문제 접근
  • 1 ~ N까지 숫자를 이어 붙혀야 하는데, N이 100,000,000이기 때문에 문제가 발생
  • 일반적인 사고 방식으로 StringBuilder를 이용하여 이어 붙일 경우 메모리 초과 발생
  • 수학적 연산이 필요
• 문제 해결
  • 일의 자리, 십의 자리, 백의 자리마다 정해진 범위가 있고 길이가 고정
    • 일의 자리 ⇒ 1 ~ 9, 길이 1
    • 십의 자리 ⇒ 10 ~ 99, 길이 2
    • 백의 자리 ⇒ 100 ~ 999, 길이 3
  • start와 end의 값을 1과 9로 셋팅을 하고 입력받은 N보다 큰 지, 작은지로 판별
  • 계산이 한 번 끝날 때마다 start와 end의 범위 증가
    • 1의 자리 ⇒ start = 1, end = 9
    • 10의 자리 ⇒ start = 10, end = 99
    • 100의 자리 ⇒ start = 100, end = 999

• 슈도 코드

N(숫자 N 저장)
start(시작값 저장), end(끝값 저장)
sum(합계 저장)
length(일의 자리 길이 1 저장)
while(start가 N이하일 때 반복){
	if(N < end){
		sum += (N - start + 1) * length
	} else {
		sum += (end - start + 1) * length
	}
	start * 10
	end * 10 + 9
	length++
}

• 코딩하기

public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int start = 1, end = 9, sum = 0, length = 1;
    while(start <= N){ // 시작값이 N 이하일 때만 실행
        if(N < end) // N이 end보다 작으면, start ~ N까지의 길이만 구함
            sum += (N - start + 1) * length;
        else // N이 end보다 크다면 start ~ end의 모든 숫자 개수 * 길이
            sum += (end - start + 1) * length;
        start *= 10;
        end = end * 10 + 9;
        length++;
    }
    System.out.println(sum);
}