[백준 알고리즘] 2231 분해합

 브루트 포스( Brute force) 

: 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법.

: 영어로 brute는 "짐승 같은, 난폭한"이라는 뜻이고, brute-force는 "난폭한 힘, 폭력"이라는 뜻이다. 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식하다고 생각할 수도 있겠지만, 항상 정확도 100%를 보장한다는 점에서 암호 해독법 중 가장 확실하고 무서운 방법이다. 

 

문제:    

https://www.acmicpc.net/problem/2231

2231번: 분해합

정리를 하면,

M의 분해합 = N <-> M은 N의 생성자

ex) 256(N) = 245(M)의 분해합

256 = 245+2+5+6

-> N이 주어졌을 때 M을 구하라.

 

 

풀이방법:    

1) 1부터 N까지의 수를 M이라 가정하고 Break_down 함수에 넣어 N의 값을 구한다.

 

ex) 256(N) = 245(M)+2+5+6

main함수에서 M은 1부터 N까지의 수를 Break_down 함수로 넘긴다. 

예를 들어 M의 값으로 240을 넘겼다고 하자.

Break_down 함수에서 M이 240이라 가정해서 구한 N은 sum의 값이다. 

우선 sum에 240을 넣는다. N의 값은 240 + 2 + 4+ 0이 되어야 한다.

식으로 고치면

240 + 0 + 4+ 2 = 240 + 240%10 +  (240/10)%10 + (240/10/10)%10 이 된다. 

따라서 이것을 코드로 작성하면 M의 값이 0이 되면 while문을 빠져 나온다.

그리고 구한 N인 sum을 리턴한다.

int Break_down(int M){
    int sum = M;
    while (1) {
        sum = sum + M % 10;
        M = M/10;
        if(M==0) break;
    }
    return sum;
}

 

2) M이라 가정해서 구한 N의 값이 실제 N과 같다면 M 출력 아니면 0 출력한다.

1부터 N까지의 수를 M이라 가정하고 Break_down 함수에 넣어 구한 N의 값(Break_down에서 리턴된 sum의 값)이 실제 N과 같다면 N의 생성자는 M이 되므로 출력하고 프로그램을 종료한다. 이때 N의 생성자 중 가장 작은 값을 구하라고 했기 때문에 바로 프로그램을 종료해야 한다.

만약, 1부터 N까지의 수를 다 확인해봤음에도, N의 생성자를 구하지 못하였다면 0을 출력하고 프로그램을 종료한다.

int main() {
    int N;
    cin >> N;
    for(int i = 1; i< N+1; i++){
        if(Break_down(i) == N){
            cout << i <<"\n";
            return 0;
        }
    }
    cout << 0 <<"\n";
    return 0;
}

 

작성한 코드는 다음과 같다. 

#include <iostream>
using namespace std;

int Break_down(int M){
    int sum = M;
    while (1) {
        sum = sum + M % 10;
        M = M/10;
        if(M==0) break;
    }
    return sum;
}


int main() {
    int N;
    cin >> N;
    for(int i = 1; i< N+1; i++){
        if(Break_down(i) == N){
            cout << i <<"\n";
            return 0;
        }
    }
    cout << 0 <<"\n";
    return 0;
}

성공한 사진!