이 문제는 주어진 자연수 n에 대해서,
이 자연수가 weird number인지 아닌지 판단하는 것입니다.
weird의 조건은 아래와 같습니다.
n의 자신보다 작은 약수들의 총합이 n보다 크고,
그 약수들 중에 몇 개를 어떻게 고르던지 그 합이 n이 될 수 없음.
저는 비효율적인 방법으로 풀었는데요,
풀고 나서, 훨씬 적은 수행시간이 드는 다른 분들의 코드를 보았으나
보면서도 알고리즘이 이해가 가지 않아 질문드리게 되었습니다.
아래 코드에서는
1. 먼저 약수를 크기가 작은 순으로 리스트에 정렬시킨다.
2. 리스트 내의 모든 수를 더한 값이 n보다 큰 동안 루프를 돌린다.
LOOP :
1) 현재 리스트 내 수의 총합에서 n을 뺀다.
2) 약수들 중에, 1)에서 구한 값 이하인 약수 중 최대를 삭제한다.
3. 남은 약수들의 합이 n과 같으면 not weird, 다르면 weird.
Signin
WEIRD 문제를 풀고 있습니다.
이 문제는 주어진 자연수 n에 대해서,
이 자연수가 weird number인지 아닌지 판단하는 것입니다.
weird의 조건은 아래와 같습니다.
저는 비효율적인 방법으로 풀었는데요,
풀고 나서, 훨씬 적은 수행시간이 드는 다른 분들의 코드를 보았으나
보면서도 알고리즘이 이해가 가지 않아 질문드리게 되었습니다.
아래 코드에서는
1. 먼저 약수를 크기가 작은 순으로 리스트에 정렬시킨다.
2. 리스트 내의 모든 수를 더한 값이 n보다 큰 동안 루프를 돌린다.
LOOP :
1) 현재 리스트 내 수의 총합에서 n을 뺀다.
2) 약수들 중에, 1)에서 구한 값 이하인 약수 중 최대를 삭제한다.
3. 남은 약수들의 합이 n과 같으면 not weird, 다르면 weird.
이 알고리즘이 어떻게 '부분 합이 n이 될 수 있는가?'를
판별할 수 있는 것일까요?
직접 값을 출력하면서 돌려보고서도 이해가 가지 않아
질문드리게 되었습니다.
알려주시면 감사하겠습니다~!
11년 전