[프로그래머스][C++] 숫자의 표현

숫자의 표현

문제 링크

숫자의 표현

분석

자연수 n을 연속된 자연수의 합으로 표현할 수 있는 경우의 수를 찾아 반환하는 문제입니다.

문제의 예시를 기준으로 15일때 다음과 같습니다.

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

예시를 보아 시작항을 기준으로 1씩 크기가 커지기 때문에, 등차수열의 합 공식으로 풀 수 있다는 것을 알 수 있습니다.
등차수열의 합에 대해서는 별도의 게시물로 정리한 적이 있으며, 현재 글에서는 간략하게 정리하겠습니다.

$ S = \frac{(a + (a + (n - 1))) \times n}{2} = \frac{(2a + (n - 1)) \times n}{2} $

여기서 S는 합, a는 첫째 항, n은 항의 개수를 의미합니다.

현재 등차수열의 합 공식으로 15의 경우의 수를 찾을 때 다음과 같습니다.

• $n = 1$
  • $\frac{(2a + 0) \times 1}{2} = 15 \Rightarrow \frac{2a}{2} = a = 15$
  • 수열 [15]
• $n = 2$
  • $\frac{(2a + 1) \times 2}{2} = 15 \Rightarrow 2a + 1 = 15 \Rightarrow 2a = 14 \Rightarrow a = 7$
  • 수열 [7, 8]
• $n = 3$
  • $\frac{(2a + 2) \times 3}{2} = 15 \Rightarrow (2a + 2) \times 3 = 30 \Rightarrow 2a + 2 = 10 \Rightarrow 2a = 8 \Rightarrow a = 4$
  • 수열 [4, 5, 6]
• $n = 4$
  • $\frac{(2a + 3) \times 4}{2} = 15 \Rightarrow (2a + 3) \times 2 = 15 \Rightarrow 4a + 6 = 15 \Rightarrow 4a = 9 \Rightarrow a = 2.25$
  • 정수가 아니기 때문에 불가능합니다.
• $n = 5$
  • $\frac{(2a + 4) \times 5}{2} = 15 \Rightarrow (2a + 4) \times 5 = 30 \Rightarrow 2a + 4 = 6 \Rightarrow 2a = 2 \Rightarrow a = 1$
  • 수열 [1, 2, 3, 4, 5]
• $n = 6$
  • $\frac{(2a + 5) \times 6}{2} = 15 \Rightarrow (2a + 5) \times 3 = 15 \Rightarrow 2a + 5 = 5 \Rightarrow 2a = 0 \Rightarrow a = 0$
  • $a = 0$이 되어 시작항이 자연수가 아니며, 이후 값에서 $a$는 음수가 되므로 더이상 불가능합니다.

풀이

int solution(int n) {
    int answer = 0;
    
    // 가능한 항의 개수만큼 반복
    // i는 항의 개수를 의미
    for (int i = 1; i * (i - 1) / 2 < n; ++i)
    {
        // 등차수열 합 공식에서 시작항을 구하기 위해 남은 값 계산
        int result = n - i * (i - 1) / 2;
        
        // 남은 값이 i로 나누어 떨어져야 a가 정수
        if (result % i == 0)
        {
            ++answer;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(\sqrt{n})$입니다.

• 가능한 항의 개수만큼 반복하는 반복문 $O(\sqrt{n})$

공간 복잡도는 추가적인 공간을 사용하지 않기 때문에 $O(1)$입니다.

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.01ms, 4.21MB) 테스트 2 〉 통과 (0.01ms, 4.2MB) 테스트 3 〉 통과 (0.01ms, 4.21MB) 테스트 4 〉 통과 (0.01ms, 4.21MB) 테스트 5 〉 통과 (0.01ms, 4.21MB) 테스트 6 〉 통과 (0.01ms, 4.21MB) 테스트 7 〉 통과 (0.01ms, 4.2MB) 테스트 8 〉 통과 (0.01ms, 4.14MB) 테스트 9 〉 통과 (0.01ms, 4.2MB) 테스트 10 〉 통과 (0.01ms, 4.2MB) 테스트 11 〉 통과 (0.01ms, 4.14MB) 테스트 12 〉 통과 (0.01ms, 4.17MB) 테스트 13 〉 통과 (0.01ms, 4MB) 테스트 14 〉 통과 (0.01ms, 4.18MB) 테스트 15 〉 통과 (0.01ms, 4.17MB) 테스트 16 〉 통과 (0.01ms, 4.2MB) 테스트 17 〉 통과 (0.01ms, 4.21MB) 테스트 18 〉 통과 (0.01ms, 4.13MB)

효율성 테스트

테스트 1 〉 통과 (0.01ms, 3.8MB) 테스트 2 〉 통과 (0.01ms, 3.89MB) 테스트 3 〉 통과 (0.01ms, 3.8MB) 테스트 4 〉 통과 (0.01ms, 3.8MB) 테스트 5 〉 통과 (0.01ms, 3.81MB) 테스트 6 〉 통과 (0.01ms, 3.89MB)