[프로그래머스/파이썬] 숫자의 표현

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

문제 링크

---

프로그래머스

---

코드

---

def solution(n):
    answer = 0
    dp=[i for i in range(1,n+1)]
    
    for i in range(n): 
        sum_dp=0
        for j in range(i,n): 
            sum_dp+=dp[j]
            if sum_dp==n:
                answer+=1
                break
            elif sum_dp>n:
                break
    return answer

---

풀이 과정&회고

---

헐 프로그래머스 Level2 문제인데… 진짜 오랜만에 아무것도 안 찾아보고!! IDE도 없이!! 20분만에 풀었다 ㅠㅠ

아이디어는 좀 늦게 떠오른 편이다. 한 10분~…? 구현하는데 얼마 안 걸려서 뿌듯하다!! 그렇게 어려운 문제는 아니었지만… 효율성 테스트도 한 번에 통과해서 기분 좋다. O(N^2)이지만... 

처음엔 DP를 이용하자고 아이디어가 떠올랐었다. 하지만 구현하고 보니 DP는 아니다. 아이디어를 떠올릴 때는 DP로 하나씩 증가시키면서 메모이제이션 기법 사용하면 되겠다~ 했지만 구현할 때 보니 그냥 이미 저장해둔 값을 사용하면 되니까 그걸 이용했다. 어쨌든… DP로부터 이미 저장해둔 리스트를 이용하는 법이 떠올랐으니… 좋은게 좋은걸로. 변수명에 DP라고 적어뒀지만 DP는 아니니 오해말길...

아무튼

풀이는 이렇다.

 

1. 1부터 n까지 저장해두는 숫자 리스트를 하나 만들어 준 후에, n만큼 루프돌면서 숫자들을 더해줄 sum_dp를 0으로 초기화한다.

2. 이중 루프 돌면서 i부터 n까지 sum_dp에 숫자들을 계속해서 더해준다.

3. 그러다보면 sum_dp가 정확히 n이 되거나, n을 초과하는 순간이 생길 것이다.

4. sum_dp가 정확히 n이 된다면 answer에 1을 더하고 break로 해당 이중루프문을 빠져 나오고, n을 초과한다면 그냥 빠져나오고 그 다음부터 또 다시 돌면서 자연수 n을 표현할 자연수를 찾으면 된다.

 

이렇게 하면 연속된 자연수를 차례대로 찾을 수 있다.

근데 다른 사람들 코드 보니까 나와 풀이가 거의 비슷하긴 한데, 리스트에 값 저장하는 것 없이 그냥 sum에 j를 더해가면서 계산했다. 아 그렇게 하면 되는 구나… 싶고 많이 배우게 된다. 역시 알고리즘 문제 풀고 나서는 다른 사람 코드도 봐야 공부가 되는 듯. 그래도 풀었으니 거기에 의의를 두기로 했다. 쉬운 문제이긴 했지만