[백준] 분해합 (BufferedReader, 2231번, 브루트 포스, Java)

문제설명

입력 & 출력

나의 풀이

 

문제를 이해하는 데 시간이 조금 걸렸습니다. 이번 "분해합"문제는 주어진 수의 가장 작은 생성자를 찾는 문제입니다.

 

문제에 입력이 216으로 주어졌을 때 해당 수의 가장 작은 생성자를 찾는 문제입니다.

 

216의 생성자는 198,207,215 가 있는데 이 중에서 가장 작은 198이 출력이 나와야합니다.

 

"가장 작은"이라는 말에서 알 수 있듯이 최솟값을 찾기 위하여 1부터 입력받은 N까지 모두 대입하면서 분해합이 입력이랑 같았지만 그 값을 반환하면 되는 문제입니다. 즉 브루트 포스 알고리즘 방식입니다.

 

• 198 = ①198 + ② 1 + ③ 9 + ④ 8 = 216
• 207 = ① 207 + ② 2 + ③ 0 + ④ 7 = 216

먼저 분해합을 찾는 함수 findAnalyzeSum 함수를 만들어줍니다.

 

① 단계 : 인자로 들어온  n을 분해합을 구하는 공식에 맞춰서 먼저 sum에 더해줍니다.

②~ ④ 단계 : n을 String으로 변환해서 str으로 저장해 주고, charAt() 메서드를 사용하여 문자열 n의 각 요소를 분리하고 다시 정수형으로 변환하여 sum에 더해줍니다.

 

다시 main문으로 들어와서 1부터 계속해서 findAnalyzeSum() 함수에 넣어주고 입력받은 n을 비교했을 때 같아지면 그 즉시 break문을 사용하여 반복문을 빠져나와야 합니다.

 

왜냐하면 문제에서 "N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오."라고 했으니 1부터 N까지 순회하는 반복문이기 때문에 조건을 만족하는 순간이 가장 작은 생성자를 찾은 순간이기 때문입니다.

 

마지막으로 가장 작은 생성자를 출력하여 마무리해 줍니다.

 

 

다른 풀이 ✅

 

브루트 포스방식인 것은 똑같지만 함수를 사용하지 않은 풀이입니다.

 

전체적인 맥락은 비슷하지만 "나의 풀이"와 다르게 문자열로 만들고 각 요소를 분리하지 않고 while문과 %,/연산을 사용해서 각 수를 분리해 줬습니다.

 

• 198 = ①198 + ② 1 + ③ 9 + ④ 8 = 216

만약에 i가 198이라면 ①단계 :198을 sum과 num에 초기화합니다.

②, ③ ,④ 단계는 다음과 같은 과정을 거칩니다.

198%10 = 8 ➡️ sum = 198 + 8

198/ 10 = 19 ➡️ num = 19

19%10 = 9 ➡️ sum = 198 + 8 + 9

19/10 = 1 ➡️ num = 1

1 % 10 = 1 ➡️ sum = 198 + 8 + 9 + 1

1 / 10 = 0 ➡️ while문 탈출

 

 

참고 ❗

[Algorithm] 완전 탐색, 브루트 포스: 가장 단순한 알고리즘(Brute Force) 알아보기