Lv2. 숫자의 표현

문제 보기 :  숫자의 표현

프로그래머스

 

---

문제

• 정답률 : 75%

---

작성 코드

def solution(n):
    num_root = [2**i for i in range(15)]
    if n in num_root:
        return 1

    if n%2==0:
        answer = 1
        k = list(i for i in range(n//2 +1))
        k = k[::-1]
    else:
        answer = 2
        k = list(i for i in range(n//3 +3))
        k = k[::-1]
        
    l = len(k) ; i = 3
    while i <= len(k): #선택 개수
        p = k[:i]
        sp= sum(p)
        if sp<n:
            i+=1
        elif sp==n:
            return answer + 1
        else:
            for j in range(len(k)-i):
                if sp==n:
                    answer += 1
                    k = k[j+1:] 
                    break
                elif sp>n: 
                    sp -= i

            i += 1
    return answer

---

풀이

코드는 생각보다 복잡하게 풀이했지만 해설은 간단할 것 같다.

코테 챌린지를 보면 몇일 동안 못 풀어서 해맸던 문젠데, 리스트나 deque 형태로 더하는 문제가 아니라
단순 덧셈으로 구하는 문제였다.

1,2,3,4,5를 더하면 15
2,3,4,5,6를 더하면 20
3,4,5,6,7를 더하면 25가 된다.

앞으로 1씩 이동하면 숫자의 개수만큼 그 합이 커진다는 말이다.

---

이러한 규칙을 먼저 정의해둔 다음, 홀수와 짝수에 따라 다른 특징도 정의했다.

홀수일 때는 2개의 원소로 무조건 나타낼 수 있다. 
예를 들어 n=15일 때, 7+8로 나타낼 수 있다.

그러나, 짝수는 2개의 원소로 나타낼 수 없다. 

이러한 규칙을 바탕으로 홀수는 기본 답을 2로 설정하고 3개의 원소부터 구하기, 짝수는 기본 답을 1로 설정하고 3개의 원소부터 구하는 것으로 두었다.

---

2의 제곱일 때도 답은 항상 1이다.

n의 maximum이 10,000이라는 점을 고려해 2^15까지를 구해둔 리스트를 하나 생성했다.