[백준알고리즘] 2231번: 분해합 -Python, C++

[백준알고리즘] 2231번: 분해합 -Python, C++

2231번: 분해합 (acmicpc.net)

2231번: 분해합

처음에 입력으로 생성자가 들어오는 줄 알고 후딱 풀어버리고는 왜 틀렸지 했다 ㅋㅋ;;

 

입력은 생성자가 아닌 분해합이 들어오며, 가능한 생성자 중 가장 작은 값을 출력하는 문제이다.

 

문제 자체는 로직이 쉬웠다.

그런데 이번에 C++로 푼 로직과 달리 예전에 파이썬으로 푼 코드가 있어서 같이 가져왔다.

---

아래는 C++ 코드다.

전체 입력 가능한 범위를 잡아 모든 수의 생성자를 구하도록 먼저 했다.

이때 더 작은 생성자의 값만 유지하도록 했다.

모든 수의 가장 작은 생성자를 저장한 이후 입력이 되는 목표값 \{n\}에 대한 생성자를 구하도록 했다.

#include <iostream>

#define ARR_SIZE 1000000 + 1

void solve(void);

int main(void)
{
	solve();
}

void solve(void)
{
	int arr[ARR_SIZE] = { 0, };
	for (int i = 1; i < ARR_SIZE; i++) // i가 생성자
	{
		int sum = i; // sum이 분해합
		int r = i;
		while (0 < r)
		{
			sum += (r % 10);
			r /= 10;
		}

		if (ARR_SIZE <= sum) break;

		if (0 == arr[sum])
			arr[sum] = i; // sum의 생성자 중 최소값은 i
	}

	int n;
	std::cin >> n;
	std::cout << arr[n];
}

 

---

아래는 파이썬 코드다. 

이때는 \(n\)까지 수를 \(1\)씩 늘려가면서 생성자인지 확인하도록 작성했다.

생성자에 해당하는 \(m\)을 \(1\)부터 시작하는 것이 아닌 \(n/2\)부터 시작하면서 효율성을 높였다.

def find(n):
    m = n//2
    while m < n:
        tm = map(int, list(str(m)))
        total = sum(tm) + m
        if total == n:
            return m
        m += 1
    return 0

    
n = int(input())

ans = find(n)
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다