글 읽기 - [자바]세용액 투포인터 문제 질문

ppungppung2 2년 전 0

혼자 풀려고 노력하다가 도움을 받고자 질문 남깁니다.

용액을 1~N+2 까지 쓸용액 무조건 하나 잡아놓고

그 다음에 고를 2개의 용액을 투포인터를 사용해서 합을 더해가며

최적의 값을 저장하게 프로그램을 작성했는데

계속 41퍼 부분에서 막히네요.

혹시 어느부분이 틀렸는지 알려주시면 감사하겠습니다.

import java.util.*;
import java.io.*;

public class Main {
  static FastReader scan = new FastReader();
  static StringBuilder sb = new StringBuilder();

  static int N;
  static int[] A;
  
  //입력 받기
  static void input() {
    N = scan.nextInt();
    A = new int[N + 1];
    for (int i = 1; i <= N; i++)
      A[i] = scan.nextInt();
  }

  static void pro() {
    //투포인터 전 배열 정렬
    Arrays.sort(A, 1, N + 1);
    //값들 초기화
    long best_sum = Long.MAX_VALUE;
    long v1=0, v2=0, v3=0;
    //1~N+2까지 무조건 사용할 용액 정하기
    for (int i = 1; i <= N - 2; i++) {
      //투포인터 L, R정의
      int L = i + 1, R = N;
      while (L < R) {
        //용액들의 총합 계산
        long sum = A[i] + A[L] + A[R];
        //가장 최적의 합이면 값 저장
        if (Math.abs(sum) < best_sum) {
          best_sum = Math.abs(sum);
          v1 = A[i];
          v2 = A[L];
          v3 = A[R];
        }
        //만약 용액 합이 0 보다 크면 값이 더 작은 용액 사용하기
        if (sum > 0)
          R--;
        //만약 용액 합이 0 보다 작으면 값이 더 큰 용액 사용하기
        else
          L++;
      }
    }
    sb.append(v1).append(' ').append(v2).append(' ').append(v3);
    System.out.println(sb);
  }

  public static void main(String[] args) {
    input();
    pro();
  }

 
  static class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    public FastReader(String s) throws FileNotFoundException {
      br = new BufferedReader(new FileReader(new File(s)));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }
  }
}

dioo1461 1년 전 1

저도 41%에서 계속 막혔었는데, 자료형 문제였습니다.

C++로 풀었는데, sum을 계산할 때 우변을 모두 연산한 뒤 sum에 집어넣는 방식이라

sum = A+B+C 에서 우변에 오버플로가 생긴 것 같습니다.

long long sum = (long long)A + B + C; 와 같이 명시적 형변환을 해주거나 입력받는 배열의 자료형을 long long으로 바꾸니 해결되었습니다.

도움이 되었으면 좋겠습니다..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[자바]세용액 투포인터 문제 질문

ppungppung2 2년 전 0

dioo1461 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말