-
백준 2231 - 분해합(JAVA)Algorithm 2022. 9. 16. 10:49728x90
9/15일에 study원들과 코테 스터디를 진행하고 뽑아 본 5개의 문제 중 하나를 풀어 보았다.
문제
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.
예제 입력 1
216
예제 출력 1
198
분해합 문제이다. 처음 문제를 볼 때 1학년 당시 했던 자릿 수 합을 생각했는데, 생성자라는 새로운 개념을 가지고 접근 하는 문제였다. 생성자로 분해합을 출력시키는 문제였다면 월등히 쉬웠을 거 같은데 분해합을 가지고 생성자를 구하는 문제이다 보니 생각보다 자꾸 헷갈려서 시간이 조금 소요된 듯 하다.
알고리즘은 간단하다.
어떤 숫자 N을 입력받는데 그 숫자가 분해합이다. 그 분해합을 만들 수 있는 최소의 생성자를 출력시키면 된다.
1. 반복문으로 1~N까지의 수를 모두 조사한다.(브루트 포스법)
2. 정해진 수를 가지고 숫자를 쪼개는 것이 아니다 보니 객관성이 있게 while문 안에서 반복적인 작업을 해주어야 한다.
3. 찾은 생성자의 분해합이 입력받은 수와 동일해 지면 그 수를 출력시키면서 반복문 종료
4. 생성자가 없는 경우는 반복문을 돌리지 않고 그냥 0 출력
나는 이렇게 해결을 했다.
num : 생성자 변수
sum : 분해합 변수
sum에 처음 부터 체크할 생성자 수 i를 담아 두면 sum 변수에 자릿수를 더하기만 하면 변수를 하나 줄이고 쉽게 해결 할 수 있다. 처음엔 변수를 두 개나 더 만들었었는데, 오히려 너무 헷갈려서 정신이 없어져 그냥 처음부터 값을 넣어서 시작하는 방법을 택했다.
이렇게 오늘도 한 문제 해결 끝!!!
728x90'Algorithm' 카테고리의 다른 글
백준 1225 - 이상한 곱셈(JAVA) (0) 2022.09.20 백준 2798 - 블랙잭(JAVA) (0) 2022.09.18 백준 1173 - 운동(JAVA) (0) 2022.09.16 백준 2292 - 벌집(JAVA) (0) 2022.09.13 3/2기록 - 백준 2635 (0) 2022.03.02