[프로그래머스] 기사단원의 무기 (Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

소스 코드

def solution(number, limit, power):
    # 범위 주의
    numbers = [0 for x in range(number+1)]

    # 1부터 number까지 포함
    for i in range(1,number+1):
        # 배수 인덱스에 +1
        for j in range(i,number//i*i+1,i):
            numbers[j] += 1
    # limit 초과시 power로 변경
    for i in range(1,number+1):
        if numbers[i] > limit:
            numbers[i] = power
    return sum(numbers)

해설

• 구현 문제
• 일종의 DP 유형

약수를 직접 구하면 안 된다!

문제 조건을 보면 기사단원의 숫자를 나타내는 number의 최댓값이 100,000입니다.

만약 각 기사단원별로 약수의 개수를 구하게 된다면 시간 초과 판정을 받을 가능성이 아주 높겠죠?

 

어차피 우리는 1부터 number까지 해당하는 모든 숫자에 대한 약수의 개수를 구해야 하므로 배수 개념으로 접근하는 것이 좀 더 좋겠습니다.

우선 numbers라는 리스트를 만들어 0부터 number 범위까지 0으로 초기화해줍니다.

이렇게 하는 이유는 인덱스가 0부터 시작이라서, 인덱스를 기준으로 배수를 찾게 되면 범위가 어긋나기 때문입니다!

 

다음으로 1부터 number까지 리스트 내 배수에 접근하여 1씩 값을 더해줍니다.

범위 설정은 다음과 같습니다.

for i in range(1,number+1):
    # 배수 인덱스에 +1
    for j in range(i,number//i*i+1,i):
        numbers[j] += 1

range(i, number // i * i + 1, i), 이것이 의미하는 바는 i부터 i 간격으로 number // i * i +1 까지입니다.

예를 들어 number = 10, i =3 이라면, 우리는 3의 배수인 3,6,9를 구해야합니다.

number 내에 3이 몇 번 들어가는지 계산해야 하므로 number // i 를 해주고 다시 i를 곱하면 number내 i의 배수 중 최댓값을 구할 수 있습니다.

 

마지막으로 numbers 리스트를 다시 돌면서 limit을 초과하는 값이 있다면 power로 변경하면 됩니다.