[伯俊2018]ショーの和5(JAVA)

🔰 質問する

💡 方法

最初はNの大きさに気づかず、好きなように解き、完全に探索して解く.
TLEはなく、パスしましたが、투포인터で解決した問題です.

📌 ダブルポインタとは?

デュアルポインタアルゴリズムは슬라이딩 윈도우とも呼ばれる.
Nの値は非常に大きく,完全ナビゲーションで解放すればタイムアウト時にポインタを解放すれば解決できる.
異なる要素を指す2つのポインタを指す1次元配列を設定します.
2つのポインタを操作することによって必要なコンテンツを取得するアルゴリズム.
例えば、N格子の1次元配列がある場合、部分配列の要素とMがある場合、個数を求める.完全に検索するとO(N^2)が出てきますが、ダブルポインタでstartポインタとendポインタを調整しながら区間和を求めるとO(N)の時間的複雑さが必要になります.
startポインタ++は、一部の配列の和を減らします.
endポインタが++の場合、部分配列の和が増加します.
この点を数の和5題に適用して解答する.

start、endポインタを設定します.start,end=0初期化

startポインタをNまで繰り返します
2-1. startポインタの増加に伴って現在の部分と
a.現在部分的にb.現在部分プラス=Nは正解+1
2-2. endポインタの増加に伴って現在の部分と
a.現在部分プラス>Nなら脱出
b.現在部分プラス=Nは正解+1

に答える

💬 ダブルポインタバージョン

import java.io.*;

public class Main_2018_2 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
	
		int start=0, end=0; //투포인터 설정
		int sum=0, cnt=0; //sum: 합, cnt: 가지수(정답)
		while(start<=N) {
			while(++end<=N) { //end 증가
				sum += end; //부분합을 증가
				if(sum>=N) {
					if(sum==N) cnt++;
					break;
				}
			}
			while(++start<=N) { //start 증가
				sum -= start; //부분합을 감소
				if(sum<=N) {
					if(sum==N) cnt++;
					break;
				}
			}	
		}
		System.out.println(cnt);
	}
}

💬 オリジナル

import java.io.*;
// 5분
public class Main_2018 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int cnt=0; //가지수(정답)
		for(int i=1;i<=N;i++) { //시작
			int sum=0;
			for(int j=i;j<=N;j++) { //시작점부터 순차적으로 더하기
				sum +=j;
				if(sum>N)
					break;
				else if(sum==N) {
					cnt++;
					break;
				}
			}
		}
		System.out.println(cnt);
	}
}

🌟 類似型の問題
2003:ツリーの和
1644:少数連続和
1806:部分和
2230:選択
1484:ダイエット
2038:古龍水熱
2531:回転寿司
2096:減少
2293:硬貨1
リファレンス
ダブルポインタ、スライドウィンドウ(修正:2019-09-09)