BOJ. 2231

#BOJ2231

분해합

드디어 무언가 알고리즘의 알을 꺼낼 수 있는 문제가 나온거 같다. 이전까지 해결하던 문제들은 대부분 수학적으로 문제를 해결할 수 있거나 간단하게 상황을 구현하면 확인할 수 있는 문제들이었다. 이 문제 같은 경우에는 브루트포스 알고리즘으로 해결하면 간단하게 해결될 것 같다. 브루트포스 알고리즘 자체는 크게 특별한 건 아니고, 그냥 전부 다 확인하는 방법이다. 사람은 백만개의 연산을 빠르게 해나가라고 하면 정신이 나가겠지만 컴퓨터는 그정도 연산은 순식간에 처리할 수 있기 때문에 그걸 활용해서 문제를 해결해 나가는 과정이라고 볼 수 있다.

이 문제에서 그렇다면 어떤 방향으로 브루트포스 알고리즘을 사용할 수 있을까? 기본적으로 이 문제는 생성자를 찾는 문제이다. 어떤 자연수의 분해합을 구하는 과정은 단순 덧셈으로만 이루어져 있다. 컴퓨터에게 주어진 수 N - 1까지의 모든 수의 분해합을 구하라하고 그 분해합 중에 N과 일치하는 것이 있다면 출력해주면 된다. 이 문제는 정말 한 번에 맞춰봐야겠다.

이 문제를 풀면서 한 번 틀렸는데 분해합이 없는 경우에 0을 출력한다는 걸 깜빡했다. 조건문을 제발 좀 잘 보자... 정답률 떨어지는 소리가 여기까지 들린다....ㅜㅜ

와 적진 않겠지만 진짜 기가 막히게 틀렸다. 도저히 모든 반례에 대해서 설명하기에는 너무 어려운 것 같아서... 그냥 브루트 포스의 개념만 이해할 수 있도록 코드만 올리도록 하겠다.

# include "iostream"
using namespace std;

int main(void){
    int N = 0;
    cin>>N;
    //아래의 for문 부분이 전부 다 확인하는 브루트포스의 과정이다.
    for (int i = 1; i < N; i++){
        int temp = i, ans = i;
        while (temp > 0){
            ans += temp % 10;
            temp = temp / 10;
        }
        if (ans == N){
            cout<<i;
            break;
        }
    }
}