[알고리즘] 프로그래머스 - 기사단원의 무기

기사단원의 무기

 

1. 구해야 하는 것
    # 총 철의 무게
2. 1을 구하기 위해 필요한 것
    # 공격력이 몇인 무기를 구매할 것인가?
        # 둘을 비교해서 넘기면 power로 공격력
            # 기사번호의 약수의 개수(=공격력)
            # 협약에 의한 제한(=limit)
    # 기사별로 공격력이 몇인 무기를 구매할지를 구한 뒤
    # 리스트를 바탕으로 철의 무게 계산
3. 그 외 고려해야 할 사항
    # number가 100000까지
    # 리스트를 먼저 만들고 비교한다.
    # 문자열로 쓰면, replace를 사용가능?

 

 

1. 풀이

# 약수 개수 구하기
a = [0]*number  # 기사 인원수만큼의 길이를 가진 리스트 생성
for i in range(1, number+1):  # 각각 기사들 한명한명에 대해
    for j in range(1, int(i**(1/2))+1):  # 기사번호의 제곱근 +1 까지 약수 개수 찾기
        # (ex.6일때 약수는 1-6, 2-3처럼 짝을 이루고 있음. 따라서 제곱근까지 구하면 시간복잡도를 줄일 수 있음)
        if i % j == 0:  # 나머지가 0이라면 약수
            if j ** 2 == i:  # 1또는 제곱수는 한개만 더해준다 > 짝이 본인이기 때문에
                a[i-1] += 1
            else:  # 그외에는 약수의 개수를 두개씩 더한다.
                a[i-1] += 2

print("ㅇ약수의 개수들 : ", a)
# 공격력 제한하기
for i in range(len(a)): # a의 인덱스를 하나씩 돌면서
    if a[i] > limit: # a의 i번째 인덱스의 값이 limit를 초과한다면,
        a[i] = power # a의 i번째 값을 power로 변경

# 필요한 철의 양(공격력들의 합) 구하기
answer = sum(a)

 

 

2. 제출용 함수

def solution(number, limit, power):
    a = [0]*number
    for i in range(1, number+1):
        for j in range(1, int(i**(1/2))+1):
            if i % j == 0:
                if j ** 2 == i:
                    a[i-1] += 1
                else:
                    a[i-1] += 2
    for i in range(len(a)):
        if a[i] > limit:
            a[i] = power
    answer = sum(a)
    return answer