[boj_2231][GO] 분해합

분해합이란?

어떤자연수 N이있을때 그 자연수 N의 분해합은

N과 N을이루는 각 자리수의 합을 의미

 

어떤자연수 M의 분해합이 N인경우

M을 N의 생성자라 한다.

 

245의 분해합?

=> 245+2+4+5+ = 256

=>245는 256의 생성자이다

(생성자는 없을수도있고, 여러개일수도있다)

 

자연수 N이 주어졌을때, N의 가장 작은 생성자를 구해야한다.

그렇다면 

i=1부터 i<=N까지를 순회하여 

i+i의자릿값의합이 N이 되는 최솟값을 출력하면 되는문제이다.

package bruteforce_problem

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func RunBoj2231() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	N, _ := strconv.Atoi(scanner.Text())

	result := 0

	for i := 1; i <= N; i++ {
		sum := i

		str := strconv.Itoa(i)

		for j := 0; j < len(str); j++ {
			num, _ := strconv.Atoi(string(str[j]))
			sum += num
		}

		if sum == N {
			result = i
			break
		}
	}

	fmt.Println(result)
}

 

그러나 N의값이높아진다면 분해합의구하는 효율은 낮아진다.

여기서우리는 규칙을 찾을 수 있다.

N의 자릿수를 d라고할때 N의 생성자는 최소한 N-9*d일것이다.

우리는 십진법으로 계산하기에, 각 자릿수가 9일때가 가장 최대치이기때문이다

따라서 i=N-9*d를 준다면, 반복문이 진행하는 범위를 좁힐 수 있다.

 

package bruteforce_problem

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func RunBoj2231Refactor() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	input := scanner.Text()
	N, _ := strconv.Atoi(input)

	result := 0
	minumum := 9 * len(input)

	for i := N - minumum; i <= N; i++ {
		sum := i
		s := strconv.Itoa(i)

		for j := 0; j < len(s); j++ {
			one, _ := strconv.Atoi(string(s[j]))
			sum += one
		}

		if sum == N {
			result = i
			break
		}
	}

	fmt.Println(result)
}