[BaekJoon/백준] 2231번

분해합 문제. 2초의 실행제한이다.

 

모든 분해합의 경우의 수에 대한 데이터. 즉 브루트포스의 결과값에 대한 데이터를 만들어 놓았다가 꺼내 쓰면 된다.

해시 함수(MD5, SHA-1, SHA-255 등)을 사용하여 만들어 낼 수 있는 값들을 왕창 저장해놓는 테이블인 '레인보우 테이블'과 같은 개념이다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] arr = new int[1000054]; // 999,999 의 분해합 = 1000053.

        for(int i=1; i<=1000000;i++) {
            int k = i;
            int total = i;
            while(k>0) {
                total += k%10;
                k /=10;
            }
            if(arr[total]==0) // 최소값만 넣을거고, 1부터 시작되므로 먼저 들어간게 최소
                arr[total] = i;
        }

        int N = Integer.parseInt(br.readLine());
        br.close();
        bw.write(""+arr[N]); bw.flush(); bw.close();

    }
}

 

실행속도를 조금이라도 더 높이기 위해 BufferedReader와 BufferedWriter를 사용했다.

이 둘을 사용하고 난 뒤에는 close를 해주는 게 필수다~!

 

---

2021.03.06

조금 더 빠르게 풀어보았다.

 

위에서는, 여러 입력을 받는 경우 도움이 되겠지만 문제에서는 한번 뿐이므로 해당 경우에 필요한 부분까지만 포문을 돌려준다.

#include <stdio.h>

int N;

int main() {
    scanf("%d", &N);
    
    for(int i = 1; i < N; i++) {
        
        int result = i;
        int temp = i;
        while( temp != 0 ) {
            
            result += temp % 10;
            temp /= 10;
            
        }
        // 분해합 찾음.
        if(result == N) {
            printf("%d", i);
            return 0;
        }
    }
    // 분해합 못찾음.
    printf("%d", 0);
}