[프로그래머스] 연습문제 > 숫자의 표현

programmers.co.kr/learn/courses/30/lessons/12924?language=python3

코딩테스트 연습 - 숫자의 표현

문제 설명

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 이하의 자연수 입니다.

---

입출력 예

nresult

15

4

입출력 예 설명

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

 

---

 

풀이

이중 for문을 돌리는데 외부 for문은 1부터 n//2+1이 범위이다.
이유는 절반을 넘어가면 더하여 원래 값을 만들어 낼 수 없기 때문이다.
예를 들어, 15라면 8을 넘어가면 더해서 만들 수 있는 숫자가 7 밖에 없다.
즉 이후는 검사할 필요가 없음.
내부 for문의 범위는 i부터 n+1인데 내부 for문은 더하기 시작할 값을 의미한다.
예로 i = 4 라면 j의 범위는 (4,16)이 되는데
내부 for문을 수행하면서 count에 j를 더해서 넣어준다.
즉 4 + 5 + 6처럼 1씩 증가하는 j값을 count와 더하고 이를
if문을 통해 주어진 n과 비교하여 같다면 정답을 +1해 주고 break 한다.
이렇게 하고 제출했더니 효율성에서 실패했다.
이유를 생각해보니. 만약 count가 n보다 커질 때의 조건 즉, else를 정의해줘야 한다.
그렇지 않으면 이미 count가 n보다 큼에도 계속해서 for문은 돌아가기 때문이다.
elif로 count > n보다 크면 break 하도록 하고 제출하니 통과했다.

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

++정답이 1부터 시작하는 것은 모든 숫자는 자기 그 자체로
표현할 수 있는 경우를 미리 더해준 것이다.
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
여기서 맨 마지막 경우 자기 그 자체를 의미한다.