21.08.13 기록

백준 알고리즘 2231 풀이

🎆나의 풀이(메모리 18.3MB, 시간 168ms로 통과)

-N의 최댓값(1,000,000)을 포함하는 크기의 배열을 선언한 후, 인덱스의 분해합을 저장했다.
-이후 입력값 N까지 인덱스를 순회하며, 생성자를 출력했다.

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;

  public class B2231 {
      public static int[] numbers = new int[1_000_000+1];

      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());

          //1부터 1,000,000까지 분해합 저장
          setConstructor();

          int res = -1;
          for(int i = 1; i < N; i++) {
              if(numbers[i] == N ) {  //가장 먼저 일치한 인덱스가 최솟값
                  res = i;
                  break;
              }
          }
          if(res < 0) { System.out.println(0); }  //res값이 초기값인 경우 0 출력
          else { System.out.println(res); }
      }

      public static void setConstructor() {
          //1의 자리
          for(int i = 1; i < 10; i++) {
              numbers[i] = (2*i);
          }

          //10의 자리
          for(int i = 10; i < 100; i++) {
              numbers[i] = (i + (i/10) + (i%10));
          }

          //100의 자리
          for(int i = 101; i < 1000; i++) {
              numbers[i] = (i + (i/100) + (i/10%10) + (i%10));
          }

          //1,000의 자리
          for(int i = 1001; i < 10000; i++) {
              numbers[i] = (i + (i/1000) + (i/100%10) + (i%100/10) + (i%10));
          }

          //10,000의 자리
          for(int i = 10001; i < 100_000; i++) {
              numbers[i] = (i + (i/10000) + (i/1000%10) + (i/100%10) + (i%100/10) + (i%10));
          }

          //100,000의 자리
          for(int i = 100001; i < 1_000_000; i++) {
              numbers[i] = (i + (i/100_000) + (i/10000%10) + (i/1000%10) + (i/100%10) + (i%100/10) + (i%10));
          }

          //1,000,000일 때
          numbers[1_000_000] = (1_000_000 + 1);
      }

🎆해설(메모리 14.2MB, 시간 136ms로 통과)

-네자릿수 N은 임의의 정수 K와 K의 각 자리수의 합과 같다.

$N_{(3)}$ = K + $k_{(1)}$ + $k_{(2)}$ + $k_{(3)}$ + $k_{(4)}$

-네자릿수 N의 각 자릿수 합의 최대는 9 + 9 + 9 + 9 이다.
-즉, 출력값(K)을 구하는 범위는 N - (9 * K의 길이) 가 된다.

K = $N_{(3)}$ - ($k_{(1)}$ + $k_{(2)}$ + $k_{(3)}$ + $k_{(4)}$)

-위 식을 활용한 코드는 아래와 같다.

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;

  public class B2231 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          String strN = br.readLine();
          int N = Integer.parseInt(strN);

          int res = 0;
          for(int i = (N - (strN.length() * 9)); i < N; i++) {
              int num = i;
              int sum = 0;

              while(num != 0) {
                  sum += (num % 10);
                  num /= 10;
              }

              if(sum + i == N) {
                  res = i;
                  break;
              }
          }
          System.out.println(res);
      }
  }