#37 알고리즘 연습 - 숫자의 표현(Python)

2019-06-06

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항

n은 10,000 이하의 자연수 입니다.

입출력 예

n	result
15	4

입출력 예 설명

입출력 예#1 문제의 예시와 같습니다.

문제풀이
연속된 숫자의 합으로 주어진 n을 표현하는 방법의 갯수를 찾는 것인데
가장 쉽게 떠올릴 수 있는 풀이로는 for문을 통해 1부터 차례대로 더하다가 n과 같으면 count
그 다음 2부터 차례대로 더하다가 n과 같으면 count…
하지만 이와 같은 방법을 사용하게 되면 이중 for문이 되기도 하고 다소 쉽게 구현할수 있으므로 다른 규칙을 찾아서 해보도록 하자
반대로 보면 주어진 n에 대해서 1로 나누면 n 자기 자신이 되고 2로 나누면 위의 예시에서는 7.5를 기준으로 앞뒤로 더해 완성해주었다. 3으로 나누었을때는 기준이 5이므로 456을 더해서 15를 완성했다 이렇게 차례대로 나누어 가며 기준점을 포함해 나누는 수만큼 더해주게 되면 n이 만들어지는지 확인할수 있다.
하지만 위의 예시에서도 볼수 있듯 6으로 나누게 되면 2.x가 나오는데 양쪽으로 6개만큼 더하기 위해서는 out of range가 나므로 따로 처리해주도록 하자.

내 풀이 🏆

def solution(n):
    answer = 0
    s_list = [i for i in range(1, n+1)]    #주어진 n을 만드는 연산에 대해 편의를 위해 list를 만들어줍니다.
    for i in s_list:                #주어진 n을 1부터 나눠보기 위해 잠시 list를 빌려 for문을 돌려줍니다.
        inter = (n//i) - (i//2)     #sum을 해줄 list의 slice의 시작점을 inter에 저장했다
         #n = 15, i = 5이면 inter은 3 - 2 이므로 1이 저장되어 slice를 1부터 해주게된다

        if inter < 1:              
         #만약 slice하는 시작점이 1보다 작아지면 slice가 되지 않으므로 바로 break 해준다 
            break

        if i % 2 == 1:              #만약 홀수이면
            if n == sum(s_list[inter-1:inter+i-1]): #n=15,i=5일때 만들어진 inter가 1이므로 s_list[0:5]이 된다[1,2,3,4,5]
                answer += 1                         #-1를 해준이유는 0번째 index가 1이기때문에 해준것이다. 
            #그리고 주어진 n과 sum의 값이 같으면 answer의 값을 증가시킨다
        else:
            if n == sum(s_list[inter:inter+i]):     #n=15, i=2일때 보면 inter 는 7-1 , 6이 되고 s_list[6:8]이 되는데
                answer += 1                         #6번째 index값이 7이기때문에 의도한대로 잘 동작함을 알 수 있다.

    return answer

다른 풀이 🏆

def expressions(num):
    answer = 0
    for i in range(1, num + 1):
        s = 0                       #for문이 돌때마다 s를 0으로 초기화 해주어 num과의 비교를 용이하게 한다
        while s < num:              
            s += i                  #s에 i = 1 일때부터 더해주는데 밑에 i+=1을 통해서 1이후에 연속된 값을
            i += 1                  #num보다 작은 순간까지 계속 더한다
        if s == num:                #while이 끝나면 s는 num보다 크거나 같은데 이때 s가 num과 같으면 answer을 증가시키고
            answer += 1

        #다시 for문의 처음으로 돌아가 s=0으로 초기화, 2부터 연속된 합을 구해서 비교한다

    return answer