연속된 자연수의 합/최대 길이 연속 부분수열

연속된 자연수의 합

✏️ 문제

* 설명
N입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 
방법의 가짓수를 출력하는 프로그램을 작성하세요.
만약 N=15이면
7+8=15
4+5+6=15
1+2+3+4+5=15
와 같이 총 3가지의 경우가 존재한다.

* 입력
첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어집니다.

* 출력
첫 줄에 총 경우수를 출력합니다.

🔍풀이

Sliding window 방법. 단, 확인은 n/2+1 까지만 해준다.

 public int solution(int n) {
        int answer = 0, sum = 0, rt = 0;
        int[] arr = new int[n]
        for(int i = 0;i < n/2+1; i++){arr[i] = i+1}
        
        for(int i = 0; i < n/2+1; i++){
        	sum += arr[i]
            if(sum == n) answer++
            while(sum >= n){
            	sum -= arr[rt++];
                if(sum == n) answer++;
            }
        }
		return answer;
}

몫과 자연수를 이용하는 방법

설명 : 연속되는 자연수의 합이 n이 되는지의 여부이기 때문에, 2개의 수의 합 ex)15 = 7+8, 3자리 수의 합 4+5+6 등 개수의 합으로 접근할 수 있다.
만약 m자리 수의 합이라면 (n-(1+2..+m))/m의 나머지가 0이라면 해당 자리수의 합으로 m을 만들 수 있다는 뜻이다.

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

최대 길이 연속 부분수열

✏️ 문제

* 설명
0과 1로 구성된 길이가 N인 수열이 주어집니다. 여러분은 이 수열에서 최대 k번을 0을 1로 변경할 수 있습니다. 여러분이 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하세요.

* 입력
첫 번째 줄에 수열의 길이인 자연수 N(5<=N<100,000)이 주어집니다.
두 번째 줄에 N길이의 0과 1로 구성된 수열이 주어집니다.

* 출력
첫 줄에 최대 길이를 출력하세요.

🔍풀이

Two pointers를 이용해 해결한다.

 public int solution(int n, int k, int[] arr) {
        int answer = 0, cnt = 0, lt = 0;
        for(int rt = 0; rt < n; rt++){
        	if(arr[rt] == 0) cnt++;
        	while(cnt > k) {
            	if(arr[lt] == 0) cnt--;
                lt++;
            }
            answer = Math.max(answer, rt - lt + 1)
        }
		return answer;
}