글 읽기 - 문제 조건이 잘못된거 같은데...

lim551 7년 전 0

제가 짠 코드가 채점중...(76%) 에서 항상 틀렸다고 나오길래 코드를 확인해봤는데 아무리 봐도 문제점을 찾지 못했습니다.

문제가 될만한 부분이라면 저는 대나무의 양이 같은 곳이 단 한 곳도 없다는 가정 하에 코드를 짰는데 이것 말고는 없다고 생각했습니다.

그래서 중간부분에 대나무 양이 같은 곳이 나오면 예외를 던지는 코드를 짜서 제출했는데 어김없이 채점중...(76%) 구간에서 런타임 에러가 뜨더군요...;

문제 수정을 하든지 테스트 입력을 수정해야 할 것 같습니다.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/************
 * <주소>		: 
 * **********
 * <해결방안>	: 
 * 
 * 정렬을 해서 가장 대나무양이 많은 지점부터 시작해봄
 * 정렬된 시작지점을 max[] 라고 하면 (max[1]은 가장 많은 곳)
 * max[1]에서는 무조건 1 (dp[1] = 1)
 * max[n]에서는 주위에 max[1 ~ n-1]이 있으면 해당 지점들 중 max값을 찾음
 * ==> dp[n] = max( max[n]보다 큰 것의 dp ) + 1 
 * 
 * **********
 * <오답노트>	: 
 * 
 * **********
 * @author LENOVO
 *
 */
public class Main {

	static int dy[] = {1, 0, -1, 0};
	static int dx[] = {0, 1, 0, -1};

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		FastScanner sc = new FastScanner();

		int n = sc.nextInt();
		int wood[][] = new int[n][n];
		Data sorted[] = new Data[n * n];	// 정렬을 위해 존재
										// data의 크기에 의해 오름차순 정렬
										// 해당 data의 x, y값을 가지고 있음
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				wood[i][j] = sc.nextInt();
				sorted[i*n + j] = new Data(wood[i][j], i, j);
			}
		}

		sort(sorted, 0, sorted.length - 1);

		// 나중에 wood 값에 대한 data나 dp의 index를 선형 시간으로 찾기 위해
		// wood 값을 임의로 변경함.
		// 문제 조건에 각 지역마다 대나무량이 다르다고 했기 때문에 문제 없음
		for(int i = 0; i < sorted.length; i++) {
			if(i < sorted.length - 1 &&
					wood[sorted[i].y][sorted[i].x] == wood[sorted[i + 1].y][sorted[i + 1].x]) {
				throw new Exception("-----ERROR: same wood-----");
			}
			wood[sorted[i].y][sorted[i].x] = i;
		}
		
		// dp[i]: i에서 시작했을 때 몇 일이나 살아남는지?
		int dp[] = new int[n * n];
		dp[sorted.length - 1] = 1;

		int max = 1;
		// i: data들 중 i번째로 작은 것
		for(int i = sorted.length - 2; i >= 0; i--) {
			int y = sorted[i].y;
			int x = sorted[i].x;
			// 갈 수 있는 곳을 가봄
			for(int direction = 0; direction < 4; direction++) {
				int ny = y + dy[direction];
				int nx = x + dx[direction];
				// 범위를 벗어났는지
				if(ny >= 0 && nx >= 0 && ny < n && nx < n) {
					// 다음 숲으로 갈 수 있으면
					if(wood[ny][nx] > wood[y][x]) {
						
						// 이렇게 index를 찾다가 시간초과
						// wood[y][x]의 값을 가진 dp의 index를 찾음
//						for(index = i + 1; index < data.length; index++) {
//							if(data[index].value == wood[ny][nx]) {
//								break;
//							}
//						}

						dp[i] = Math.max(dp[i], dp[wood[ny][nx]]);
					}
				}
			}
			dp[i]++;
			max = Math.max(dp[i], max);
		}
		System.out.println(max);
	}

	/**
	 * 퀵소트
	 * 
	 * @param data 정렬할 배열
	 * @param l 처음: 0
	 * @param r 처음: length - 1
	 */
	public static void sort(Data[] data, int l, int r){
		int left = l;
		int right = r;
		int pivot = data[(l+r)/2].value;

		do{
			while(data[left].value < pivot) left++;
			while(data[right].value > pivot) right--;
			if(left <= right){    
				Data temp = data[left];
				data[left] = data[right];
				data[right] = temp;
				left++;
				right--;
			}
		}while (left <= right);

		if(l < right) sort(data, l, right);
		if(r > left) sort(data, left, r);
	}

	static class Data {
		public int value;
		public int y;
		public int x;

		public Data(int value, int y, int x) {
			this.value = value;
			this.y = y;
			this.x = x;
		}
	}
}
class FastScanner {
	BufferedReader br;
	StringTokenizer st;

	public FastScanner(String s) {

		try {

			br = new BufferedReader(new FileReader(s));
		} catch (FileNotFoundException e) {
			throw new RuntimeException(e);
		}
	}

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

	}

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

	int nextInt() {

		return Integer.parseInt(nextToken());
	}

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

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

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

}

game2k 7년 전 0

"각 지역마다 대나무의 양이 다르다." 라고 되어있는데 두개 이상의 지역에 같은 양의 대나무가 있는 경우 오답 나게 하니까 틀리네요.

현재 정답 소스로는

1 1

인 경우 답이 1이 나오는데 문제 조건상 이런 테스트 케이스가 있으면 안되는거 아닌가요

lim551 7년 전 0

대나무 양이 같은 경우 처리를 해주니 성공했습니다.

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

문제

문제

출처

ICPC

문제 조건이 잘못된거 같은데...

lim551 7년 전 0

game2k 7년 전 0

lim551 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말