본문 바로가기

CS/알고리즘

[TIL] 20240306 16일차

백준 문제 2231번: 분해합

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

 

2231번: 분해합

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이

www.acmicpc.net

 

 

시행착오 코드 1

https://www.acmicpc.net/source/74489955

 

로그인

 

www.acmicpc.net

더보기
val = input()
digit = len(val)
val_raw = int(val)
min_sum = val_raw
for i in range(1, digit * 9):
    tmp = val_raw - i
    tmp_result = tmp + sum([int(x) for x in str(tmp)])
    if tmp_result == val_raw:
        min_sum = tmp if min_sum > tmp else min_sum

print(min_sum)

처음엔 입력받은 숫자(분해합)의 자릿수를 고려해서 확인할 숫자 범위(range)를 생각하려고 했다.

그러나 이 코드는

- 생성자를 찾지 못했을 경우 처리하는 부분 없음

- 자릿수가 하나인 경우 tmp가 음수가 되는 문제

이라는 문제점이 있다.

시행착오 코드 2에선 두번째 문제를 해결하기 위해 자릿수를 고려하는 것을 삭제, 입력받은 숫자까지만큼 for문이 돌도록 처리했다.

 

 

시행착오 코드 2

https://www.acmicpc.net/source/74490007

 

로그인

 

www.acmicpc.net

더보기
val_raw = int(input())
min_sum = val_raw
for i in range(1, val_raw + 1):
    tmp = val_raw - i
    tmp_result = tmp + sum([int(x) for x in str(tmp)])
    if tmp_result == val_raw:
        min_sum = tmp if min_sum > tmp else min_sum

print(min_sum)

이 코드는

- 생성자를 찾지 못했을 경우 처리하는 부분 없음

이라는 문제를 여전히 해결하지 못한 상태였다.

 

그러나 이 문제를 계속 찾지 못하고

tmp = val_raw - i 에서 반복문을 끝까지 돌았을 때 tmp가 0이 된다는 점

min_sum을 갱신하는 부분에서 tmp가 0일 때 min_sum이 0으로 갱신될거란 말도 안되는 착각을 하고 있었다.

(이 착각의 원인은 위의 if tmp_result == val_raw 조건문을 전혀 생각하지 않았기 때문이다.)

 

 

결국 해설을 보고 나서 문제를 정확하게 인지하고 수정한 코드가 아래의 코드이다.

https://www.acmicpc.net/source/74529735

 

로그인

 

www.acmicpc.net

더보기
# 입력 값 처리
val = input()
val_raw = int(val)

# 최소 생성자 변수의 초기값 설정
min_sum = val_raw

for i in range(1, val_raw + 1):
    # 입력한 분해합 값에서 1씩 감소시키면서 생성자인지 아닌지 확인
    # tmp: 입력한 분해합 값에서 1 감소시킨 값
    # tmp_result: tmp가 생성자인지 아닌지 확인하기 위해 분해합 계산
    tmp = val_raw - i
    tmp_result = tmp + sum([int(x) for x in str(tmp)])
    # tmp의 분해합이 입력한 분해합과 같다면
    # 최소 생성자 변수 min_sum의 값을 갱신
    if tmp_result == val_raw:
        # 로직 상 if else 문을 사용할 필요가 없어 삭제.
        # 삭제 이유: min_sum은 값이 갱신될 때 항상 이전 값보다 작은 값으로 갱신되므로 비교할 필요가 없음
        # min_sum = tmp if min_sum > tmp else min_sum
        min_sum = tmp

# 만약 어떠한 생성자를 찾지 못했다면 min_sum을 0으로 변경
if min_sum == val_raw:
    min_sum = 0

# min_sum 출력
print(min_sum)

 

그러나 이 코드도 사실 최적화가 되지 않은 코드다. (이건 해설을 보고 알았다.)

내 코드에선 '최소 생성자 변수' 라는 것을 정의했는데 이게 필요가 없다.

내가 작성한 코드의 로직을 정확하게 반대로 진행하면 된다.

 

입력한 분해합 값에서 1씩 감소시키는 것이 아니라, 그냥 i 자체를 생성자인지 아닌지 확인하면 된다.

이를 반영한 코드는 아래와 같다.

더보기
val_raw = int(input())
for i in range(1, val_raw + 1):
    result = i + sum([int(x) for x in str(i)])
    if result == val_raw:
        print(i)
        break
    if i == val_raw:
        print(0)

 

'CS > 알고리즘' 카테고리의 다른 글

[TIL] 20240312 20일차  (0) 2024.03.12
[TIL] 20240311 19일차  (0) 2024.03.12
[TIL] 20240308 18일차  (0) 2024.03.08
[TIL] 20240307 17일차  (0) 2024.03.07
[TIL] 20240305 15일차  (2) 2024.03.05