숫자의 표현

문제 설명

---

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

---

입출력 예 설명

입출력 예#1

문제의 예시와 같습니다.

---

문제 풀이

방정식을 활용하여 풀이

인수 k는 연속된 숫자를 의미

인수 n은 임의의 숫자

x는 연속된 숫자 중 가장 작은 수를 의미

---

효율성 미 통과 코드 (3중 for문 사용으로 시간복잡도 증가)

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        // k는 도는 연속수의 갯수
        for (int k = 1; k <= n; k++) {
            for (int x = 1; x <= n; x++) {
                int sum = 0;
                for (int i = 1; i < x; i++) {
                    sum += i;
                }
                int j = (k * x) + sum;

                if (j == n) {
                    answer++;
                }
            }
        }

        return answer;
    }
}

---

정답 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
				

//k는 몇연속인지의 대한 갯수

        for (int k = 1; k <= n; k++) {
            for (int x = 1; x <= n; x++) {
                int j = (k * x) + (x * (x - 1)) / 2;
                if (j > n) {
                    break;
                }
                if (j == n) {
                    answer++;
                }
            }
        }

        return answer;
    }
}