글 읽기 - 어디가 틀렸는지 모르겠습니다 ㅠㅠ(주석有)

slave_fromnowon 7년 전 1

x, y 지점에서 dir 방향으로 이동할때 현재까지 저장된 선분들과 부딪히는지 확인했습니다.

답글들에 있는 테스트 케이스를 돌려보아도 모두 정상적인 값들로 나오는데 어디서 틀렸는지 모르겠습니다 ㅠㅠ

n이 0일때도 처리를 해줬습니다!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int l;
	static int n;
	static int[] time;
	static char[] direction;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		l = Integer.parseInt(br.readLine().trim());

		n = Integer.parseInt(br.readLine().trim());
		time = new int[n + 1];
		direction = new char[n + 1];

		String[] input = null;
		for (int i = 0; i < n; i++) {
			input = br.readLine().trim().split(" ");
			time[i] = Integer.parseInt(input[0]);
			direction[i] = input[1].charAt(0);
		}
		ArrayList<Line> line = new ArrayList<>();	//지나온 선분들 기록
		// 초기 경계 선분 추가
		line.add(new Line(-l - 1, -l - 1, l + 1, -l - 1));
		line.add(new Line(-l - 1, -l - 1, -l - 1, l + 1));
		line.add(new Line(-l - 1, l + 1, l + 1, l + 1));
		line.add(new Line(l + 1, -l - 1, l + 1, l + 1));

		time[n]=Integer.MAX_VALUE;	//모든 상황 다 돌아도 안부딪혔을 때를 대비
		
		int x = 0;
		int y = 0;
		int dir[] = { 0, 1 };// 처음에는 우측방향
		Line currLine = null;

		long result = 0;

		for (int i = 0; i <= n; i++) {
			int t = Integer.MAX_VALUE; // t를 최대한 갈 수 있다고 가정
			for (int j = 0; j < line.size(); j++) {// 현재 방향으로 갈 수 있는 최대 시간 구하기
				currLine = line.get(j);

				if (currLine.dir == 0) {// 가로 선분?
					// 현재 (x,y)에서 (dir[0],dir[1])방향으로 해당 선분까지 갈 수 있는 최대
					if (dir[0] == 0 && dir[1] == 1) {// 우측방향?
						if (x == currLine.x1 && y < currLine.y1) { // 우측으로 쭉가다가
																	// 해당 가로 선분의
																	// 왼쪽 지점 만났을
																	// 경우
							t = Math.min(t, currLine.y1 - y);
						}
					} else if (dir[0] == 0 && dir[1] == -1) {// 좌측 방향?
						if (x == currLine.x1 && y > currLine.y2) { // 좌측으로 쭉가다가 해당 가로 선분의 오른쪽 지점 만났을 경우
							t = Math.min(t, y - currLine.y2);
						}
					} else if (dir[0] == -1 && dir[1] == 0) {// 위쪽?
						if (x > currLine.x1 && y >= currLine.y1 && y <= currLine.y2) {
							t = Math.min(t, x - currLine.x1);
						}
					} else {// 아래쪽?
						if (x < currLine.x1 && y >= currLine.y1 && y <= currLine.y2) {
							t = Math.min(t, currLine.x1 - x);
						}
					}

				} else {// 세로 선분?
					if (dir[0] == 0 && dir[1] == 1) {// 우측방향?
						if (y < currLine.y1 && x >= currLine.x1 && x <= currLine.x2) {
							t = Math.min(t, currLine.y1 - y);
						}
					} else if (dir[0] == 0 && dir[1] == -1) {// 좌측 방향?
						if (y > currLine.y1 && x >= currLine.x1 && x <= currLine.x2) {
							t = Math.min(t, y - currLine.y1);
						}
					} else if (dir[0] == -1 && dir[1] == 0) {// 위쪽?
						if (y == currLine.y1 && x > currLine.x2) {
							t = Math.min(t, currLine.x2 - x);
						}
					} else {// 아래쪽?
						if (y == currLine.y1 && x < currLine.x1) {
							t = Math.min(t, currLine.x1 - x);
						}
					}
				}
				
			}//end j
			if (t <= time[i]) { // 지나온 모든 선분을 확인했을 때 부딪히는 상황이었다면
				result += t;
				System.out.println(result);
				return;
			}
			result += time[i]; // 안 부딪혔으면?
			// 회전 후 다음 이동 전의 마지막 좌표
			 int newX=x+time[i]*dir[0];
			 int newY=y+time[i]*dir[1];
			dir = turn(dir, direction[i]);// 회전!
			line.add(new Line(x, y, newX, newY));	//지나온 새로운 선분 추가
			x=newX;
			y=newY;
		}//end i

	}
	/**선분*/
	static class Line {
		int x1, y1, x2, y2;
		int dir;

		public Line(int x1, int y1, int x2, int y2) {
			super();
			this.x1 = x1;
			this.x2 = x2;
			this.y1 = y1;
			this.y2 = y2;
			if (x1 == x2) {
				dir = 0; // 가로 선분
				if(y1>y2){
					int temp=y2;
					y2=y1;
					y1=temp;
				}
			} else {
				dir = 1; // 세로 선분
				if(x1>x2){
					int temp=x2;
					x2=x1;
					x1=temp;
				}
			}
			
		}

		@Override
		public String toString() {
			return "Line [x1=" + x1 + ", y1=" + y1 + ", x2=" + x2 + ", y2=" + y2 + ", dir=" + dir + "]";
		}

	}

	/**회전 후 다음 진행방향 구하는 메서드*/
	public static int[] turn(int[] d, char turn) {// 현재 방향, 도는 방향
		// 현재 오른쪽일 경우
		if (d[0] == 0 && d[1] == 1) {
			// 좌회전
			if (turn == 'L') {
				// 위쪽 방향으로
				return new int[] { -1, 0 };
			} else {// 우회전
					// 아래쪽 방향으로
				return new int[] { 1, 0 };
			}

		} else if (d[0] == -1 && d[1] == 0) {// 현재 위쪽방향일 경우
			if (turn == 'L') {

				return new int[] { 0, -1 };
			} else {
				return new int[] { 0, 1 };
			}
		} else if (d[0] == 0 && d[1] == -1) { // 현재 왼쪽방향일 경우
			if (turn == 'L') {

				return new int[] { 1, 0 };
			} else {
				return new int[] { -1, 0 };
			}

		} else { // 현재 아래쪽 방향일 경우
			if (turn == 'L') {
				return new int[] { 0, 1 };
			} else {
				return new int[] { 0, -1 };
			}
		}
	}

}

kdk8361 7년 전 1

int제한 넘어갈겁니다.

slave_fromnowon 7년 전 1

long으로 다 변경해도 13%에서 틀리네요 ㅠㅠ 혹시 반례가 뭘까요?

kdk8361 7년 전 1

4
6
2 L
1 R
1 R
3 R
2 R
1 L

16 나와야 하는데 얼마나오시나요?

slave_fromnowon 7년 전 1

네 정상적으로 16 나옵니다 ㅜㅜ

아래껀 long으로 수정한 코드에요.

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

public class Main {
	static long l;
	static int n;
	static long[] time;
	static char[] direction;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		l = Long.parseLong(br.readLine().trim());

		n = Integer.parseInt(br.readLine().trim());
		time = new long[n + 1];
		direction = new char[n + 1];

		String[] input = null;
		for (int i = 0; i < n; i++) {
			input = br.readLine().trim().split(" ");
			time[i] = Long.parseLong(input[0]);
			direction[i] = input[1].charAt(0);
		}
		ArrayList<Line> line = new ArrayList<>();	//지나온 선분들 기록
		// 초기 경계 선분 추가
		line.add(new Line(-l - 1, -l - 1, l + 1, -l - 1));
		line.add(new Line(-l - 1, l + 1, l + 1, l + 1));
		line.add(new Line(l + 1, -l - 1, l + 1, l + 1));
		line.add(new Line(-l - 1, -l - 1, -l - 1, l + 1));

		time[n]=Long.MAX_VALUE;	//모든 상황 다 돌아도 안부딪혔을 때를 대비
		
		long x = 0;
		long y = 0;
		int dir[] = { 0, 1 };// 처음에는 우측방향
		Line currLine = null;

		long result = 0;

		for (int i = 0; i <= n; i++) {
			long t = Long.MAX_VALUE; // t를 최대한 갈 수 있다고 가정
			for (int j = 0; j < line.size(); j++) {// 현재 방향으로 갈 수 있는 최대 시간 구하기
				currLine = line.get(j);

				if (currLine.dir == 0) {// 가로 선분?
					// 현재 (x,y)에서 (dir[0],dir[1])방향으로 해당 선분까지 갈 수 있는 최대
					if (dir[0] == 0 && dir[1] == 1) {// 우측방향?
						if (x == currLine.x1 && y < currLine.y1) { // 우측으로 쭉가다가
																	// 해당 가로 선분의
																	// 왼쪽 지점 만났을
																	// 경우
							t = Math.min(t, currLine.y1 - y);
						}
					} else if (dir[0] == 0 && dir[1] == -1) {// 좌측 방향?
						if (x == currLine.x1 && y > currLine.y2) { // 좌측으로 쭉가다가 해당 가로 선분의 오른쪽 지점 만났을 경우
							t = Math.min(t, y - currLine.y2);
						}
					} else if (dir[0] == -1 && dir[1] == 0) {// 위쪽?
						if (x > currLine.x1 && y >= currLine.y1 && y <= currLine.y2) {
							t = Math.min(t, x - currLine.x1);
						}
					} else {// 아래쪽?
						if (x < currLine.x1 && y >= currLine.y1 && y <= currLine.y2) {
							t = Math.min(t, currLine.x1 - x);
						}
					}

				} else {// 세로 선분?
					if (dir[0] == 0 && dir[1] == 1) {// 우측방향?
						if (y < currLine.y1 && x >= currLine.x1 && x <= currLine.x2) {
							t = Math.min(t, currLine.y1 - y);
						}
					} else if (dir[0] == 0 && dir[1] == -1) {// 좌측 방향?
						if (y > currLine.y1 && x >= currLine.x1 && x <= currLine.x2) {
							t = Math.min(t, y - currLine.y1);
						}
					} else if (dir[0] == -1 && dir[1] == 0) {// 위쪽?
						if (y == currLine.y1 && x > currLine.x2) {
							t = Math.min(t, currLine.x2 - x);
						}
					} else {// 아래쪽?
						if (y == currLine.y1 && x < currLine.x1) {
							t = Math.min(t, currLine.x1 - x);
						}
					}
				}
				
			}//end j
			if (t <= time[i]) { // 지나온 모든 선분을 확인했을 때 부딪히는 상황이었다면
				result += t;
				System.out.println(result);
				return;
			}
			result += time[i]; // 안 부딪혔으면?
			// 회전 후 다음 이동 전의 마지막 좌표
			long newX=x+time[i]*dir[0];
			long newY=y+time[i]*dir[1];
			dir = turn(dir, direction[i]);// 회전!
			line.add(new Line(x, y, newX, newY));	//지나온 새로운 선분 추가
			x=newX;
			y=newY;
		}//end i

	}

	static class Line {
		long x1, y1, x2, y2;
		int dir;

		public Line(long x1, long y1, long x2, long y2) {
			super();
			this.x1 = x1;
			this.x2 = x2;
			this.y1 = y1;
			this.y2 = y2;
			if (x1 == x2) {
				dir = 0; // 가로 선분
				if(y1>y2){
					long temp=y2;
					y2=y1;
					y1=temp;
				}
			} else {
				dir = 1; // 세로 선분
				if(x1>x2){
					long temp=x2;
					x2=x1;
					x1=temp;
				}
			}
			
		}

		@Override
		public String toString() {
			return "Line [x1=" + x1 + ", y1=" + y1 + ", x2=" + x2 + ", y2=" + y2 + ", dir=" + dir + "]";
		}

	}

	// 왼: 1, 오: 2, 상:3, 하:4
	public static int[] turn(int[] d, char turn) {// 현재 방향, 도는 방향
		// 현재 오른쪽일 경우
		if (d[0] == 0 && d[1] == 1) {
			// 좌회전
			if (turn == 'L') {
				// 위쪽 방향으로
				return new int[] { -1, 0 };
			} else {// 우회전
					// 아래쪽 방향으로
				return new int[] { 1, 0 };
			}

		} else if (d[0] == -1 && d[1] == 0) {// 현재 위쪽방향일 경우
			if (turn == 'L') {

				return new int[] { 0, -1 };
			} else {
				return new int[] { 0, 1 };
			}
		} else if (d[0] == 0 && d[1] == -1) { // 현재 왼쪽방향일 경우
			if (turn == 'L') {

				return new int[] { 1, 0 };
			} else {
				return new int[] { -1, 0 };
			}

		} else { // 현재 아래쪽 방향일 경우
			if (turn == 'L') {
				return new int[] { 0, 1 };
			} else {
				return new int[] { 0, -1 };
			}
		}
	}

}

kdk8361 7년 전 1

line 함수를 보니 가로선분, 세로선분일 때를 나눠 y2>y1, x2>x1을 유지하게 만드려고 하신거 같은데 그러면 대입할 때 this.을 넣어줘야 하는거 아니에요?

slave_fromnowon 7년 전 1

감사합니다 ㅠㅠ this로 바꿨더니 36프로로 넘어갔어요...

근데 그 이후로는 또 안 넘어가네요 ㅠㅠ 반례가 있을까요

slave_dragon 7년 전 1

코드가 구리네요 다시 짜셔야 할듯 ㅋ

slave_fromnowon 7년 전 1

용수같네요!

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠습니다 ㅠㅠ(주석有)

slave_fromnowon 7년 전 1

kdk8361 7년 전 1

slave_fromnowon 7년 전 1

kdk8361 7년 전 1

slave_fromnowon 7년 전 1

kdk8361 7년 전 1

slave_fromnowon 7년 전 1

slave_dragon 7년 전 1

slave_fromnowon 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말