백준 문제 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 |