[백준으로 배우는 Swift] 분해합 (백준 2231번)

1. 시작하며

[백준 - 단계별로 풀어보기] 중, 브루트 포스 단계의 분해합 문제를 풀게 되었다.

문제를 처음 접했을 땐 굉장히 어렵다고 느껴졌지만 브루트 포스에 대한 개념을 익히니 크게 어렵지 않은 문제였다.

브루트 포스에 대한 개념을 이해하면서 분해합 문제를 풀어보도록 하자

2. 브루트 포스

브루트 포스 공격(brute-force attack, 무차별 대입 공격)은 암호학에서 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다.

예를 들어, 4자리 수의 비밀번호를 풀기 위해 0000 ~ 9999 범위의 모든 숫자를 대입해 보는 것이다.

따라서 알고리즘 문제에 대입하여 보면, ‘모든 경우의 수를 대입해 정답을 찾는 방법’ 이라고 이해할 수 있겠다.

출처 : https://ko.wikipedia.org/wiki/무차별_대입_공격

3. 백준 2231번 - 분해합

그러면 분해합 문제를 보도록 하자.

분해합 문제는, 분해합으로 이루어진 입력 N을 받아 N의 생성자를 출력해야 한다.

단, N을 이루는 생성자가 없을 경우 0을 출력해야 한다.

이 문제는 브루트 포스의 개념을 모르고 보면 어떤 수학적 알고리즘을 찾아야 하는지 고민하게 될 것이다.

본인도 이 알고리즘을 찾기 위해 많은 시간을 쏟았지만 브루트 포스를 이해하고 나선 크게 어렵지 않은 문제였다.

let N = Int(readLine()!)!

func disassembledSum(number: Int) -> Int {
    var num = 0
    // 입력값 N의 범위 : 1 ~ 1,000,000
    for i in 1...1000000 {
        // 1부터 1,000,000까지 모두 시도
        num = i

        // 각 자리수 별로 더해주기 위해 String으로 변환
        let stringInt = String(i)

        // n은 String.element이기 때문에 다시 String으로 변환 후 Int형으로 변환
        for n in stringInt {
            let nums = Int(String(n))!
            num += nums
        }

        // number(입력값 N)와 동일할 경우 리턴
        if num == number {
            return i
        }
    }

    // 1부터 1,000,000까지의 경우의 수를 시도했음에도 일치하지 않을 경우 0 리턴
    return 0
}

print(disassembledSum(number: N))

입력값 N을 만드는 생성자를 찾기 위해 1부터 1,000,000까지의 모든 수를 분해합 시키면서 N과 일치하는지 비교하였다.

일치할 경우 그 값을 출력, 아닐 경우 0을 출력하도록 하였다.

4. 마무리

브루트 포트 방식으로 모든 수를 대입하니 크게 어려움 없는 문제였다.

문제에 대한 수학적 알고리즘을 찾아 해결하려는 접근은 좋지만 그 문제의 출제의도와 목표 주제를 이해하면 앞으로 문제를 푸는데 더욱 도움이 될 것이라 생각한다.

문제참고 : https://sapjilkingios.tistory.com/m/54