![[2231번] 분해합](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbcwRn2%2Fbtqw3PadtSF%2FqrrI4QUIQrCKn8BMeQkIhK%2Fimg.png)
반응형
2231번: 분해합
문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그
www.acmicpc.net
- 분해합: 어떤 자연수 $N$이 있을 때, $N$과 $N$이 이루는 각 자리수의 합
자연수 하나가 주어졌을 때, 다른 자연수의 분해합을 통해 그 자연수가 만들어진다면 만들어지는 다른 자연수 중 가장 작은 생성자 자연수를 구하는 문제입니다.
시간 제한은 '2초'로 두고 있고, 입력하는 자연수 $N$은 범위가 $1 \leq N \leq 1,000,000$입니다.
처음부터 하나하나 계산해서 구해도 시간은 절대 2초를 넘어갈 수 없다는 것을 알 수 있습니다.
즉, 브루트 포스(Brute Force) 알고리즘으로 쉽게 풀 수 있는 문제라는 뜻입니다.
이후는 구현만 해주시면 쉽게 풀 수 있습니다.
반응형