[알고리즘 문제 풀이] - 숫자의 표현

문제를 읽어보니까 Finn이라는 친구가 수학을 참 좋아하나 보네요...ㅎ

 

문제가 그리 어려워 보이진 않네요.

 

주어진 숫자를 연속된 숫자로 표현하는 방법이 몇가지나 있나 찾는 거군요.

 

 

<생각의 과정>

1. nested loop을 써서 1부터 더해보자. 그 다음은 2 그다음은 3 이런식으로...

 

2. 문제가 너무 쉽게 풀린다. nested loop이니 효율성을 고려해보자

 

3. 일단 위에서 모든 숫자는 덧셈 없이 그대로 표현할수 있는 한가지 방법이 있으니 최소 1이다

 

<풀이>

def solution(n):
    answer = 1
    middle = int(n/2)
    for i in range(1,middle+1):
        temp = 0
        for j in range(i,middle+2):
            temp += j
            if temp == n:
                answer += 1
                break
            elif temp > n:
                break
    return answer

 

loop을 돌릴때 굳이 1부터 n까지 볼게 아니라 n의 반값 까지만 돌렸습니다.

 

그 이상의 연속된 숫자들을 더하면 n보다 큰 숫자가 만들어지기 때문입니다.

 

안쪽 loop에서 숫자들을 더해가다가 n과 같으면 즉시 loop을 브레이크 하고

 

또 n 이상 큰 숫자가 만들어지게 되면 브레이크를 걸도록 했습니다.

 

결과는

 

음.. 우선 다 통과가 되긴 했네요

 

효율성 케이스들의 런타임을 보니까 loop에 브레이크를 넣지 않았다면

 

아마 시간 초과가 나오지 않았을까 싶네요..

 

제출하고 다른 사람들의 풀이를 보는게

 

프로그래머스의 재미 중에 하나죠

 

공식이 있었네요...

 

이런 풀이는 도대체 어떻게 생각해 낼수 있는걸까요

 

참 신기합니다