글 읽기 - 반례나 틀린부분 찾아주시면 감사드리겠습니다 ㅠㅠ

laughter 7년 전 0

시간 초과로 감 못잡다가 밑에 분 코드 보고 다시 풀어봤는데 60% 정도에서 틀리네요...

밑에 나와있는것들 테스트 해봐도 다 됐는데 반례를 도저히 못찾겠습니다..

틀린 부분이나 반례 찾아주시면 감사하겠습니다 ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

class Line{
	long start_x;
	long start_y;
	long end_x;
	long end_y;
	
	Line(long x1, long x2, long y1, long y2){
		start_x = x1;
		start_y = y1;
		end_x = x2;
		end_y = y2;
	}
}


public class Main {
	
	static int N;
	static long L;
	static ArrayList<Line> list;
	static long[] sec;
	static int[] dir;
	static long head_x;
	static long head_y;
	static int cur_dir;
	static long result;
	
	public static boolean move(long sec, int dir){
		int[] move_x = {1,0,-1,0};
		int[] move_y = {0,1,0,-1};
		
		long new_x = head_x+move_x[cur_dir]*sec;
		long new_y = head_y+move_y[cur_dir]*sec;
		
		Line temp = new Line(head_x,new_x,head_y,new_y);
		
		if(!check(temp))
			return false;
		else{
			head_x = new_x;
			head_y = new_y;
			result += sec;
			list.add(temp);
			cur_dir = (cur_dir+dir)%4;
			return true;
		}
	}
	
	static boolean check(Line temp){
		long min = Long.MAX_VALUE;
		boolean flag = true;
		
		for(int i =0; i<list.size(); i++){
			if(list.get(i).end_x==temp.start_x&&list.get(i).end_y==temp.start_y)
				continue;
			else{
				 long distance = intersect(list.get(i),temp);
				 if(distance != 0){
					 min = Math.min(min, distance);
					 flag = false;
				 }
			}
		}
		
		if(!flag){
			result +=min;
			return false;
		}
		else if(temp.end_x>L){
			result += L-temp.start_x+1;
			return false;
		}
		else if(temp.end_x<-L){
			result += Math.abs(-L-temp.start_x)+1;
			return false;
		}
		else if(temp.end_y>L){
			result += L-temp.start_y+1;
			return false;
		}
		else if(temp.end_y<-L){
			result += Math.abs(-L-temp.start_y)+1;
			return false;
		}
		return true;
	}
	
	public static long intersect(Line pre, Line cur){
		long big_x = 0, big_y = 0, small_x = 0, small_y = 0;
		
		if(pre.start_x==pre.end_x){ //세로
			big_x = pre.end_x;
			small_x = pre.start_x;
			if(pre.end_y>pre.start_y){
				big_y = pre.end_y;
				small_y = pre.start_y;
			}
			else{
				big_y = pre.start_y;
				small_y = pre.end_y;
			}
		}
		else if(pre.start_y==pre.end_y){ //가로
			big_y = pre.end_y;
			small_y = pre.start_y;
			if(pre.end_x>pre.start_x){
				big_x = pre.end_x;
				small_x = pre.start_x;
			}
			else{
				big_x = pre.start_x;
				small_x = pre.end_x;
			}
		}
		
		if( (pre.start_x==pre.end_x) && (cur.start_x==cur.end_x)){ //둘 다 세로
			if( (pre.start_x==cur.start_x) && (small_y<=cur.end_y)&& (cur.end_y<=big_y)){
				return Math.min(Math.abs(big_y-cur.start_y), Math.abs(small_y-cur.start_y));
			}
			else
				return 0;
		}
		
		else if( (pre.start_y == pre.end_y) && (cur.start_y == cur.end_y)){
			if( (pre.start_y == cur.start_y) && (small_x<=cur.end_x)&&(cur.end_x<=big_x)){
				return Math.min(Math.abs(big_x-cur.start_x), Math.abs(small_x-cur.start_x));
			}
			else
				return 0;
		}
		
		else if ( (pre.start_x == pre.end_x) && (cur.start_y == cur.end_y)){
			if( (small_y<= cur.start_y && cur.start_y<=big_y) && (Math.min(cur.start_x,cur.end_x)<=pre.end_x&&Math.max(cur.start_x, cur.end_x)>=pre.end_x)){
				return Math.abs(cur.start_x-pre.end_x);
			}
			else
				return 0;
		}
		else if( (pre.start_y==pre.end_y)&&(cur.start_x==cur.end_x)){
			if((small_x<=cur.start_x&&cur.start_x<=big_x)&&(Math.min(cur.start_y, cur.end_y)<=pre.start_y&&pre.start_y<=Math.max(cur.start_y, cur.end_y))){
				return Math.abs(cur.start_y-pre.start_y);
			}
			else
				return 0;
		}
		return -1;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		L = Long.parseLong(br.readLine());
		N = Integer.parseInt(br.readLine());
		list = new ArrayList<Line>();
		sec = new long[N];
		dir = new int[N];
		head_x = 0;
		head_y = 0;
		cur_dir = 0;
		boolean flag = true;
		
		for(int i = 0; i<N; i++){
			String[] line = br.readLine().split(" ");
			sec[i] = Long.parseLong(line[0]);
			if(line[1].equals("L"))
				dir[i] = 1;
			else
				dir[i] = 3;
		}
		
		for(int i = 0; i<N; i++){
			flag = move(sec[i], dir[i]);
			if(!flag)
				break;
		}
		
		if(flag==true) //아무것도 아니면 죽을때 까지 이동
			flag = move(2*L+1,-1);
		
		System.out.println(result);
		
	}

}

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

문제

문제

출처

ICPC

반례나 틀린부분 찾아주시면 감사드리겠습니다 ㅠㅠ

laughter 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말