5624.良い方法

8588 ワード
シミュレーション DP boj テキストリンク
1.問題リンク
2.参照リンク

1.トラブルシューティング


「質問」タブにヒントがあります.
A+B+C=X、すなわち「i個の数より前の3個の数の和」である.
A+B+C=XはA+B=X-Cと同じ意味です.
すなわち,現在のi個数を基準として,以前の数から得られた値(X−C)を減算して以前に一度やったことがあれば,問題の条件に合致する.
したがって,Xの値を得る前に,A+Bの値を採取する.

2.ソースコード

//좋은 수
import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int [] array = new int[n];
		
		for(int i =0 ; i < n ; i ++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		
		int mid = 200000;
		boolean [] visited =new boolean[mid*2+1];
		
		int ans =0 ;
		for(int i =0 ; i < n ; i++) {
			for(int j =0 ; j < i ; j++) {
				if(visited[array[i] - array[j] + mid]) {
					ans++;
					break;
				}
			}
			
			for(int j =0 ; j <= i ; j++) {
				visited[array[i] + array[j] + mid ] = true;
			}
			
		}
		
		System.out.println(ans);
	}

}
typography
BOJ 18406ラッキーストレート