[문제풀이] 03-05. 연속된 자연수의 합

인프런, 자바(Java) 알고리즘 문제풀이

Two pointers, Sliding window - 0305. 연속된 자연수의 합

---

🗒️ 문제

---

🎈 나의 풀이

	private static int solution(int n) {
        int answer = 0, sum = 0, r = 1, l = 1;

        while(r < n) {
            if(sum == n) {
                answer++;
                sum += r++;
            } else if(sum < n) {
                sum += r++;
            }
            else {
                sum -= l++;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(solution(n));
    }

---

🖍️ 강의 풀이

    public int solution(int n, int m, int[] arr){
		int answer=0, sum=0, lt=0;
		for(int rt=0; rt<n; rt++){
			sum+=arr[rt];
			if(sum==m) answer++;
			while(sum>=m){
				sum-=arr[lt++];
				if(sum==m) answer++; 
			}
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++){
			arr[i]=kb.nextInt();
		}
		System.out.print(T.solution(n, m, arr));
	}

---

💬 짚어가기

해당 문제는 앞에서 풀이한 연속 부분 수열 문제와 핵심 로직이 동일하다.

나의 풀이의 경우 n부터 m까지의 누적합을 검사하고, 조건에 따라 n 또는 m을 증가시키는 방식으로 구현했다.
강의에서는 이전 문제와 동일하게 배열을 생성하여 풀이했다.

---

🖌️ 문제 풀이 - 수학적 접근

해당 문제를 수학적인 알고리즘으로 풀이할 수 있다.
🔖 자연수 $k$가 $n$개의 자연수로 나눌 수 있는지 판별하기

1. $k$에서 $1$부터 $n$까지 합한 수를 뺀다.
2. $k - n(n+1)/2$에 $n$으로 나눈 후 나머지를 확인한다.
3. $(k - n(n+1)/2)$ mod $n$의 값이 $0$이면 참, 그렇지 않으면 거짓이다.

	public int solution(int n){
		int answer=0, cnt=1;
		n--;
		while(n>0){
			cnt++;
			n=n-cnt;
			if(n%cnt==0) answer++;
		}
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		System.out.print(T.solution(n));
	}