[백준 2331번] 분해합

2231번: 분해합

---

문제 상황

자연수 245의 분해합은 256(=245+2+4+5)이 된다.

자연수 256의 생성자는 245이다.

자연수 N이 주어졌을 때 N의 가장 작은 생성자를 구해내는 프로그램을 만들어보자.

 

즉, 자연수 N에 대해서 생성자를 만족하는 수를 구하는 것이 이번 문제의 핵심이다.

---

솔루션

생성자가 분해합을 하는 절차를 보고 주어진 자연수 N에 대한 생성자를 구해내는 솔루션을 적용했다.

(분해합 = 245 + 2 + 4 + 5)

 

따라서, 자연수 1 ~ 자연수 N-1까지의 수를 모두 분해합 연산을 진행시켜

주어진 N의 생성자가 되는지 확인하여 생성자를 찾아냈다.

 

---

솔루션 코드 작성 (with 파이썬)

아래는 다음 솔루션을 적용해 파이썬으로 작성한 코드이다.

# 백준 2231 분해합

# 분해합 입력받음
n = int(input(""))

# 생성자 변수
answer = 0

# 생성자 판별 조건연산
for i in range(n-1, 1, -1):

  # 임의 생성자
  m = i
  i_sag = []
  for z in str(i):
    i_sag.append(z)
  for x in range(len(i_sag)):
    m += int(i_sag[x])

  if(n == m):
    answer = i

print(answer)

---

마치며

이 문제를 푸는데 걸린 시간은 대략 2시간 정도이다.

시간이 오래걸렸다..

문제를 처음에 접근했던 방식이 복잡했기에 코드로 구현하면서 애를 많이 먹었다.

 

복잡했던 처음 방법 (수식으로 접근)

문제를 처음 보자마자 분해합에 대한 생성자들을 찾아내는 문제라고 생각했다.

그래서, 분해합을 기준으로 생성자로 분해합 조건을 달성하는 수식을 써내려갔다.

1의 자리부터 시작해 1,000,000 자리까지 "분해합 = 생성자 변수를 포함한 수식"을 정의했다.

 

해당 수식은 나눗셈 연산과 나머지 연산을 이용해 각 자릿수의 값을 구해

생성자에 대한 분해합 연산식을 구성했다.

하지만, 파이썬 코드로 수식을 이용해 코드를 작성하는 방법이 복잡해 보였기에..

이 방법은 시도해보지 않았다.

 

아마, 아래의 코드가 "분해합 = 생성자 변수를 포함한 수식"으로 접근한 솔루션일 것이다.

아래의 코드처럼 구현하는 역량을 지닐 수 있을 때까지 좀 더 노력해보겠다 ㅎㅎ..

n = int(input())
for i in range(1, n+1):
    original = i
    g = i
    while i != 0:
        g += i % 10
        i //= 10
    if n == g :
        print(original)
        break
if original == n :
    print(0)

 

파이썬 자료구조 List를 이용한 솔루션 (자료구조의 중요성..)

앞서 말했듯이, 첫번째 접근 방법은 주어진 자연수 N에 대한 생성자를 판별하는 수학적 수식을

구성해 접근했다.

수학적 수식을 구성하긴 했지만, 코드로 구현함에 있어서 어려움으로 포기를 하게 되었다.

그렇게 구현방법을 고민하던 중

각 자릿수를 List를 이용해 추출할 수 있다는 것을 알게되었다.

(각 자릿수를 수식으로 추출하기엔 복잡해서, 다른 방법이 있나, 구글로 찾아봄..)

 

복잡한 수식으로 전개되어 각 자릿수 값을 구하는 것과 대조되어

List를 이용하더니, 코드 구현이 정말 간단했다. 

number = 123
a = []
for i in str(number):
    a.append(i)

 

그렇게, 각 자릿수를 구하고자

수식으로 복잡하게 구성했던 걸 뒤로하고,

자연수 1 ~ N - 1 까지, List를 이용해 각 자릿수 값을 구한 후 모두 분해합을 진행시켜

주어진 자연수 N에 대한 최소 생성자를 찾아냈다.

 

따라서,

이번 문제 풀이 경험을 통해 자료구조를 이해하고 있다면,

동일한 알고리즘에 대해 쉽게 구현할 수 있다는 사실을 깨달았다.

다만, 최적화에 대해선 수학적 수식이 월등하다는 것도 숙지하고 있어야 한다.

앞으로 더 많은 문제를 풀어봄으로써, 자료구조를 이용해 복잡한 알고리즘들을 구현할 수 있도록 하겠다.