[백준 2231번] 분해합 (C++)

1. 문제

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

2231번: 분해합

 

2. 풀이

아이디어

제한 시간이 2초인 만큼 모든 수를 선형탐색해도 시간이 넉넉하다. 따라서 1부터 N까지 반복문을 다음 수를 만들면 된다. 분해합이 N이 되는 순간 반복문을 멈추고 바로 답을 출력하면 통과 시간을 최대한 빠르게 할 수 있다.

분해합을 구하는 과정은 [자릿수 분해] 알고리즘을 사용한다. 

알고리즘 순서

1. 1 ~ N까지 반복문을 돌며 현재의 숫자의 분해합을 만든다.
2. i번째 숫자로 만들 수 있는 분해합이 N이 된 순간 반복문을 멈추고 답을 출력한다.

구현

#include<iostream>
using namespace std;

int N, ans;
bool flag;

void constructure(int n){
    int sum = n;
    int temp = n;
    while(n != 0){
        sum += n % 10;
        n /= 10;
    }
    if(sum == N) {
        flag = true;
        ans = temp;
    }
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin >> N;
    for(int i=1; i<=N; i++) {
        constructure(i);
        if(flag) break;
    }
    if(flag) cout << ans;
    else cout << 0;
    return 0;
}

 

알고리즘 분석

위의 알고리즘의 시간 복잡도는 O(N)이다. 최악의 경우(N = 10⁶일 때 분해합이 존재하지 않는 경우) O(N) = 10⁶이므로 2초의 시간내에 충분히 통과가능하다. 다만 원하는 조건이 나왔을 경우 탐색을 멈추면 조금 더 빠른 시간내에 통과할 수 있다.

[두 방법의 시간 복잡도 비교]

1 ~ N까지 완전 탐색을 하였을 경우

원하는 조건이 나왔을 때 탐색을 멈춘 경우

두 방식의 시간 복잡도는 10배 넘게 차이가 나는 것을 알 수 있다.

 

3. 정리

자릿수 분해를 연습하기 좋은 문제다. 다음은 이와 비슷한 문제이다.

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

4673번: 셀프 넘버

 

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

12348번: 분해합 2