boj 1253

우선 해당 문제는 처음으로 한 생각은 조합으로 풀어 보자 였다 .

private static void dfs(int start, int sum){
	if(start == 2){
    	if(sum <= n){
        	check[sum] = true;
        }
    }
    
    for(int i=0; i<n; i++){
    	if(!visited[i]){ // 조합 자기 자신을 빼야하므로 중복 조합 x
        	visited[i] = true;
            dfs(start+1,sum+arr[i]);
            visited[i] = false;
        
        }
    }

}

이런식으로 조합을 sum을 구하여 boolean 배열 check에 해당 값을 넣어 후에 check에서 true만 꺼내 수를 세어 주려 하였다

결과는

우선 시간 초과이고 또 고려를 안한게 있었다.

자신을 제외하고 두개의 합이 자신이 되는것을 찾아야 했다.

문제 해결

시간 초과를 해결하기 위해 투퍼인터 기법을 도용하였다

start = 0;
end = n-1;

0. for 문으로 현재 요소 i 를 추출 한다
1. start 가 end보다 커지면 종료
2. start 와 end 의 합이 현재 요소 보다 크면 end -
3. start 와 end의 합이 현재 요소 보다 작으면 start 를 +
4. 만약 합이 현재 요소와는 같다면 start end 가 현재 요소인지 확인(현재 요소이면 안되기 때문)

for(int i=0; arr.length; i++){
	start = 0;
    end = n-1;
    
    while(start < end){ // 1. 
    	//2 
        sum = arr[start] + arr[end];
        
        if(sum > i){ //2
        	end --;
        }
        if(sum  < i ){//3
        	start ++
        }
        
        if(sum == i){//4
        	if(i!=start && i != end){
            	count++;
            }else if(start == i ){
            	start ++;
            }else{
            	end --;
            }
  
        
        }
    	
    }

}

전체 코드

private static int[] arr;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        arr = new int[n];
        visited = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);


        int count= 0;
        for(int i=0; i<n; i++) {
            int start = 0;
            int end = n-1;


            int target = arr[i];
            while(start < end){

                // 두 수
                int sum = arr[start] + arr[end];


                if(sum > target) { // 타깃 보다 크면
                    end = end -1;
                }else if(sum <target ) {
                    start = start +1;
                }else { // start == target
                    if(i != start && i!= end) { // 자신을 제외

                    }else if(i==start) {
                        start = start +1;
                    }else {
                        end = end-1;
                    } // 0 0 0 0 1


                }

            }

        }




        System.out.println(count);
    }

---

투포인터 문제는 더 풀어봐야 감을 잡을 거 같다 그리고 문제를 잘 읽자