문제풀이 - java 백준 1748 수 이어쓰기

 

 

 

 

 

 

문제

 

요약하자면 n을 입력한후 그 n까지 1부터 적어서 총 몇개까지 나오는지 구하는거다.

 

 

풀이

 

n이 1의 자리면 1씩증가시킬 것이고
n이 10의 자리면 2씩증가해서
주어진 범위에서 최대로 갯수가 존재할 수 있음을 알았다.
1~9 -> 1*9 (1이 9개)
10~99 -> 2*90 (2씩 90개)
100~999 -> 3*900 (3씩 900개)
1000~ 9999 -> 4*9000 (4씩 9000개)

 

위와 같은 조건으로 다 if 문 걸을려고 했다.
저번에 푼 문제에서 시간초과가 나온 경험으로 이렇게 푸는건 바로 아닌 것같다.

 

하나하나 나열해봤다.
n<10 일때 1*9 개
n<100 일때 2*90 + 9 개
n<1000 일때 3*900 + 2*90 + 9 개

 

규칙을 찾았고 반복문을 통해 저 규칙을 반복시키려고 했다.

 

우선 입력받은 n이 몇자린지 구했다.
10씩 나누어주고 leongth++ 변수로 몇자린지 셌다.

 

 

while(n > 0){
      n /=10;
      length ++;
    }

 

주어진 n의 자릿수보다 한자릿수 적게 최대 나올 수 있는 갯수:
[count = nine(9) * 몇의자리 + 누적 count]
i는 1부터 < length까지 (length보다 1개 적게 실행)
이렇게 예를들어 n=123을 입력하면 count는 189개가 된다.

 

for(int i = 1 ; i< length; i++){
      count = nine*i + count;
      nine*=10;
    }

 

temp = 그 자릿수보다 한자리 작은 최대나올 수 있는 수 구했다.
예를들어 n = 123이면 temp = 99다.

 

int temp = (int)(Math.pow(10,length-1)-1);

 

total = (입력한 num - 한자리작은 최대 수 ) * 자릿수 (만큼늘어나니깐) + 이때까지 구한 count

로 최종 출력해줬다.

 

import java.util.Scanner;

public class Baekjoon_1748 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int num = sc.nextInt();
    int length = 0; // 입력해준 num 
    int count = 0;  // 입력해준 num보다 한자리작을때 나올수있는 최대갯수
    int total = 0;  // 최종값
    int nine = 9;   // 계산위한 값

    int n = num;  
    while(n > 0){  	// 길이 구하기
      n /=10;
      length ++;
    }

    // 입력해준 num보다 한자리작을때 나올수있는 최대갯수
    for(int i = 1 ; i< length; i++){  
      count = nine*i + count;
      nine*=10;


    }
	
    // 입력한 num보다 한자리 작은 최대 수
    int temp = (int)(Math.pow(10,length-1)-1);
    // 구해놓은 최대 갯수(count) + num보다 한자리 작은 최대 수에서의 갯수
    total = (num-temp)*length + count;

    System.out.println(total);


  }
}

 

 

회고

 

어려웠다. 이런 계산문제를 저번에 풀었던 카잉달력을 떠올렸다. 그때도 하나씩 나열한 뒤 규칙을 찾았고, 거기서 연산을 이용해서 규칙을 찾았다.
저번에는 나혼자 풀기 어려웠지만 오늘은 그래도 혼자 알고리즘을 풀었다. 한 문제 씩 풀다보니 점점 실력이 나아진듯 하다. 기쁘다. 꾸준히하자.