[BOJ]1253号:いいですね(Java)


質問する (Gold 4)


1253号:はい

に答える


配列中の値を1つずつ回転させ,その数が良いか否かを二重ポインタで判別する.
問題の例はあまりにも自業自得であるため,以下の例として問題を解く.
5
-2 0 1 2 3
  • は基本的にソートされます.そうでなければ、デュアルポインタの移動に基づいて論理を記述することはできません.
  • 左、右の値を設定します.ソートのために右の値をi-1に設定することはできません.
    ->負数があるので私より大きく、私も出てくる可能性もあるので
  • の各ポインタ値の合計がまたはより大きい場合は、小数を加算し、正しい値を移動します.
    逆に、私より小さい場合は、もっと大きな数を加算するので、左の値を移動します.
  • コード#コード#

    package implement;
    
    import java.util.*;
    import java.io.*;
    
    public class BOJ_1253_좋다 {
        public static void main(String[] args) throws Exception{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());
            int[] numbers = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i =0 ; i < N ; i++){
                numbers[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(numbers);
            int result = 0;
            for(int i = 0 ; i < N ; i++){
                int left = 0;
                int right = N-1;    // 음수값이 있음에 유의!
                while(true){
                    // 현재 나(i)의 위치에 있는 경우
                    if(left == i) left++;
                    else if(right == i) right--;
    
                    // 결과를 찾을 수 없다.
                    if(left >= right) break;
    
                    // 정렬이 되어 있으므로, 합이 더 크다면 더 작은 수와 더해주어야 하니까 왼쪽으로 움직이는 right 값을 변경
                    if(numbers[left] + numbers[right] > numbers[i]) right--;
                    else if(numbers[left] + numbers[right] < numbers[i]) left++;
                    else{      // 좋다!
                        result++;
                        break;
                    }
                }
            }
            System.out.println(result);
        }
    
    }

    送信



    最初はずっと試していたが、数日後になってやっと解法を思いついた.