BOJ 9506. [Bronze1] 약수들의 합

[hojongs]

Problem link

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

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

Pseudo-code

idea를 수도 코드로 작성해본다

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys

readl = sys.stdin.readline


def f():
    while True:
        n = int(readl())
        if n < 0:
            break

        # 약수들을 구한다 (소인수 분해가 아니다)
        divisors = ["1"]
        # 약수들의 합을 구한다
        summ = 1
        for i in range(2, (n >> 1) + 1):
            if n % i == 0:
                divisors.append(str(i))
                summ += i

        # 출력
        if summ == n:
            print(f'{n} = {" + ".join(divisors)}')
        else:
            print(f"{n} is NOT perfect.")


f()

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

• 에라토스테네스의 체: n 이하의 소수 알고리즘
• 유클리드 호제법: 최대 공약수 알고리즘
• 소인수 분해 != 약수

구현력: 알고리즘을 신속, 정확하게 구현했는가?