글 읽기 - 36%에서 자꾸만 틀립니다..ㅜ

alswls822 7년 전 0

다른 분들 질문도 보고 올려주신 반례도 해결하면서 정답은 출력되는 것 같은데

36%에서 왜 어떤 부분에서 틀리는지 모르겠습니다.

알려주시면 감사하겠습니다ㅜㅜ

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

public class Main {
	static long L;
	static int cur_dir;
	static long head_x;
	static long head_y;
	static ArrayList<Line> list;
	static long total_time;
	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());
			head_x = 0;
			head_y = 0;
			cur_dir = 0;
			int N = Integer.parseInt(br.readLine());
			long[] time = new long[N];
			String[] dir = new String[N];
			list = new ArrayList<Line>();
			boolean flag = true;
			for(int i=0;i<N;i++)
			{
				String[] line = br.readLine().split(" ");
				time[i] = Long.parseLong(line[0]);
				dir[i] = line[1];
			}
			for(int i=0;i<N;i++)
			{
				flag = move(time[i],dir[i]);
				if(flag == false)
					break;
			}
		
			if(flag==true)
				flag = move(2*L+1,"N");
			
			System.out.println(total_time);
	}
	static boolean move(long time,String dir)
	{
		int[] dir_x = {1,0,-1,0};
		int[] dir_y = {0,1,0,-1};
	
		long new_x = head_x+dir_x[cur_dir]*time;
		long new_y = head_y+dir_y[cur_dir]*time;
		Line temp = new Line(head_x,head_y,new_x,new_y);
		if(!check(temp))
			return false;
		else
		{
			head_x = new_x;
			head_y = new_y;
			total_time += time;
			list.add(temp);
		}
		
		if(dir.equals("L"))
			cur_dir = (cur_dir+1)%4;
		else if(dir.equals("R"))
			cur_dir = (cur_dir+3)%4;
	
		return true;
	}
	static boolean check(Line temp)
	{
		long min = Long.MAX_VALUE;
		boolean flag = true;
		if(temp.end_x>L)
		{
			total_time += L-temp.start_x+1;
			return false;
		}
		else if(temp.end_x<-L)
		{
			total_time += Math.abs(-L-temp.start_x)+1;
			return false;
		}
		else if(temp.end_y>L)
		{
			total_time += L-temp.start_y+1;
			return false;
		}
		else if(temp.end_y<-L)
		{
			total_time += Math.abs(-L-temp.start_y)+1;
			return false;
		}
		else if(!list.isEmpty())
		{
			for(int i=0;i<list.size();i++)
			{		
				long big_x = list.get(i).end_x;
				long big_y = list.get(i).end_y;
				long small_x = list.get(i).start_x;
				long small_y = list.get(i).start_y;
				if((big_x==temp.start_x && big_y==temp.start_y))
					continue;
				else if(big_x==small_x && big_y!=small_y)
				{
					if(big_y < small_y)
					{
						long t = big_y;
						big_y = small_y;
						small_y = t;
					}
					if(temp.end_x==temp.start_x)			
					{
						if(temp.end_x!=big_x || (temp.end_x==big_x && !((big_y>=temp.end_y&&small_y<=temp.end_y) || (big_y>=temp.start_y&&small_y<=temp.start_y)) ))
							continue;		//서로 평행이면서 안겹칠때
						else				//평행이면서 겹칠때
						{
							min = Math.min(min,Math.min(Math.abs(big_y-temp.start_y),Math.abs(small_y-temp.start_y)));
							flag = false;
						}
					}
					else
					{	
						if(temp.end_y <= big_y && temp.end_y >= small_y && big_x<=Math.max(temp.end_x,temp.start_x) && big_x>=Math.min(temp.end_x,temp.start_x))	//가로 * 세로
						{
							min = Math.min(min,Math.abs(big_x - temp.start_x));
							flag = false;		//서로 수직이면서 겹칠때
						}
						else					//수직이면서 안겹칠때
							continue;
					}
				}
				else if(big_y==small_y && big_x!=small_x)
				{
					if(big_x < small_x)
					{
						long t = big_x;
						big_x = small_x;
						small_x = t;
					}
					if(temp.end_y==temp.start_y)			
					{
						if(temp.end_y!=big_y || (temp.end_y==big_y && !((big_x>=temp.end_x&&small_x<=temp.end_x) || (big_x>=temp.start_x&&small_x<=temp.start_x)) ))
							continue;				//서로 평행이면서 안겹칠때
						else						//평행이면서 겹칠때
						{
							min = Math.min(min,Math.min(Math.abs(big_x-temp.start_x),Math.abs(small_x-temp.start_x)));
							flag = false;
						}
					}
					else 
					{
						if(temp.end_x <= big_x && temp.end_x >= small_x && big_y<=Math.max(temp.end_y,temp.start_y) && big_y>=Math.min(temp.end_y,temp.start_y))	//가로 * 세로
						{
							min = Math.min(min,Math.abs(big_y - temp.start_y));
							flag = false;			//서로 수직이면서 겹칠때
						}							
						else						//안겹칠때
							continue;
					}
				}
			}
		}
		if(!flag)
		{
			total_time += min;
			return false;
		}
		return true;
	}
 	static class Line{
		long start_x;
		long start_y;
		long end_x;
		long end_y;
		Line(long s_x,long s_y,long e_x,long e_y)
		{
			this.start_x = s_x;
			this.start_y = s_y;
			this.end_x = e_x;
			this.end_y = e_y;
		}
	}
}

kdk8361 7년 전 0

1 L

1 R

10 L

5나와야 하는데 11이 나오실듯 합니다.

alswls822 7년 전 0

kdk8361

도움주셔서 감사합니다ㅜㅜ

덕분에 68%까지 갔습니다 코드도 다시한번 정리했습니다.

도대체 또다른 무슨 반례가 있을까요ㅜㅜ

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

public class Main {
	static long L;
	static int cur_dir;
	static long head_x;
	static long head_y;
	static ArrayList<Line> list;
	static long total_time;
	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());
			head_x = 0;
			head_y = 0;
			cur_dir = 0;
			int N = Integer.parseInt(br.readLine());
			long[] time = new long[N];
			String[] dir = new String[N];
			list = new ArrayList<Line>();
			boolean flag = true;
			for(int i=0;i<N;i++)
			{
				String[] line = br.readLine().split(" ");
				time[i] = Long.parseLong(line[0]);
				dir[i] = line[1];
			}
			for(int i=0;i<N;i++)
			{
				flag = move(time[i],dir[i]);
				if(flag == false)
					break;
			}
		
			if(flag==true)
				flag = move(2*L+1,"N");
			
			System.out.println(total_time);
	}
	static boolean move(long time,String dir)
	{
		int[] dir_x = {1,0,-1,0};
		int[] dir_y = {0,1,0,-1};
	
		long new_x = head_x+dir_x[cur_dir]*time;
		long new_y = head_y+dir_y[cur_dir]*time;
		Line temp = new Line(head_x,head_y,new_x,new_y);//System.out.println(head_x+"  "+head_y+"  "+new_x+"   "+new_y);
		if(!check(temp))
			return false;
		else
		{
			head_x = new_x;
			head_y = new_y;
			total_time += time;
			list.add(temp);
		}
		
		if(dir.equals("L"))
			cur_dir = (cur_dir+1)%4;
		else if(dir.equals("R"))
			cur_dir = (cur_dir+3)%4;
	
		return true;
	}
	static boolean check(Line temp)
	{
		long min = Long.MAX_VALUE;
		boolean flag = true;
		if(!list.isEmpty())
		{
			for(int i=0;i<list.size();i++)
			{		
				if((list.get(i).end_x==temp.start_x && list.get(i).start_y==temp.start_y))
					continue;
				else 
				{
					long result = intersect(list.get(i),temp);
					if(result!=0)
					{
						min = Math.min(min,result);
						flag = false;
					}
				}
			}
		}
		if(!flag)
		{
			total_time += min;
			return false;
		}
		else if(temp.end_x>L)
		{
			total_time += L-temp.start_x+1;
			return false;
		}
		else if(temp.end_x<-L)
		{
			total_time += Math.abs(-L-temp.start_x)+1;
			return false;
		}
		else if(temp.end_y>L)
		{
			total_time += L-temp.start_y+1;
			return false;
		}
		else if(temp.end_y<-L)
		{
			total_time += Math.abs(-L-temp.start_y)+1;
			return false;
		}
		return true;
	}
	static long intersect(Line a,Line b)		//겹치면 true, 안겹치면 0
	{
		long big_x=0,big_y=0,small_x=0,small_y=0;
		if( a.start_x == a.end_x )
		{
			big_x = a.start_x;small_x = a.end_x;
			if(a.start_y > a.end_y)
			{
				big_y = a.start_y;
				small_y = a.end_y;
			}
			else
			{
				big_y = a.end_y;
				small_y = a.start_y;
			}
		}
		else if( a.start_y == a.end_y )
		{
			big_y = a.start_y;small_y = a.end_y;
			if(a.start_x > a.end_x)
			{
				big_x = a.start_x;
				small_x = a.end_x;
			}
			else
			{
				big_x = a.end_x;
				small_x = a.start_x;
			}
		}
		if( (a.start_x==a.end_x) && (b.start_x==b.end_x) )		//둘 다 세로일때
		{
			if(a.start_x==b.start_x && small_y<=b.end_y && b.end_y<=big_y)
				return Math.min(Math.abs(big_y-b.start_y),Math.abs(small_y-b.start_y));
			else
				return 0;
		}	
		else if( (a.start_y==a.end_y) && (b.start_y==b.end_y) )	//둘 다 가로일때
		{
			if(a.start_y==b.start_y && small_y<=b.end_y && b.end_y<=big_y)
				return Math.min(Math.abs(big_y-b.start_y),Math.abs(small_y-b.start_y));
			else
				return 0;
		}
		else if( (a.start_x==a.end_x) && (b.start_y==b.end_y) )	//a세로  b가로
		{
			if( (small_y<=b.end_y && b.end_y<=big_y) && (Math.min(b.start_x,b.end_x)<=a.start_x && a.start_x<=Math.max(b.start_x,b.end_x)))
				return Math.abs(a.start_x-b.start_x);
			else
				return 0;
		}
		else if( (a.start_y==a.end_y) && (b.start_x==b.end_x) )	//a가로  b세로
		{
			if( (small_x<=b.end_x && b.end_x<=big_x) && (Math.min(b.start_y,b.end_y)<=a.start_y && a.start_y<=Math.max(b.start_y,b.end_y)))
				return Math.abs(a.start_y-b.start_y);
			else
				return 0;
		}
		return -1;
	}
 	static class Line{
		long start_x;
		long start_y;
		long end_x;
		long end_y;
		Line(long s_x,long s_y,long e_x,long e_y)
		{
			this.start_x = s_x;
			this.start_y = s_y;
			this.end_x = e_x;
			this.end_y = e_y;
		}
	}
}

kdk8361 7년 전 0

1 L

2 L

1 L

2 R

6인데 얼마나오시나요?

둘다 가로일때 왜 다 y로 연산을 하시죠? x로 연산하셔야 할거 같은데요.

alswls822 7년 전 0

실수햇네요ㅜㅜ 그치만 똑같이 틀립니다 휴....

kdk8361 7년 전 2

1 L

2 L

1 L

5 R

6나와야 하는데 얼마나오나요?

alswls822 7년 전 0

감사합니다 드디어됐네요ㅜㅜ

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

문제

문제

출처

ICPC

36%에서 자꾸만 틀립니다..ㅜ

alswls822 7년 전 0

kdk8361 7년 전 0

alswls822 7년 전 0

kdk8361

kdk8361 7년 전 0

alswls822 7년 전 0

kdk8361 7년 전 2

alswls822 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말