글 읽기 - 질문드립니다 (틀렸습니다)

jin3670 5년 전 0

* 풀이 전략
* 0. 초기화 (N과 L)
* 1. 높이 차이 함수 생성 ( int diffH (int a, int b)
* 2. 행, 열 방향으로 순회한다. ( 종과 횡으로 이동하는 함수는 중복 코드가 발생 )
* 3. 높이 차이 (h), 길의 길이 (l)을 계산한다.
* 4. 상승 하는 경우 지금까지 평지였던 부분이 L 이상
* 5. 하강 하는 경우 하강후 L 만큼의 길이의 평지가 존재
* 6. 하강 후 상승 (110011 L=2)일 경우 방향이 바뀌는거 고려
* 7. 하강 후 상승 (11000011 L=2) 일 경우 방향이 바뀌지만 2개의 다리를 놓을 수 있는것 고려
* 8. 결과 res 출력

요구 사항에 맞게 하나씩 구현해 가는 방식으로 풀어나갔습니다.

질문에 나와있는 반례는 다 정확한 답을 찾는데, 어디서 반례가 발생할 수 있는지 도움 요청 드립니다.

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

public class Main {
	public static int N, L;
	public static int[][] map;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] NM = br.readLine().split(" ");
		N = Integer.parseInt(NM[0]);
		L = Integer.parseInt(NM[1]);
		
		// 0. initialize
		map = new int[N][N];
		for(int i=0; i<N; i++) {
			String[] temp = br.readLine().split(" ");
			for(int j=0; j<temp.length; j++) {
				map[i][j] = Integer.parseInt(temp[j]);
			}
		}
		System.out.println(solve()+solve2());
	}
	//2. 행, 열 방향으로 순회
	public static int solve() {
		int result = 0;
		
		//횡으로 이동
		for(int i=0; i<N; i++) {
			int l = 1;
			int diff = 0;
			boolean isdown = false;
			for(int j=1; j<N; j++) {
				diff = diffH(map[i][j-1], map[i][j]);
				if(Math.abs(diff)>1) break;
				if(diff == 0) {
					l++;
				} else {
					// 상승
					if(diff < 0) {
						// 한번 하강했으면 l의 두배의 길이가 필요로 한다.
						if(isdown) if(l < 2*L) break;
						if(l < L) break;
						isdown = false;
					}
					// 하강
					else {
						isdown = true;
						int tempL = 0;
						for(int k=0; k<L; k++) {
							if(j+k == N) break;
							if(map[i][j+k] == map[i][j]) {
								tempL++;
							}
						}
						if(tempL < L) break;
					}
					if(j!=N-1) l=1;
				}
				if(j==N-1) {
					if(l<L) break;
					result++;
				}
			}
		}
		return result;
	}
	public static int solve2() {
		int result = 0;
		//종으로 이동
		for(int i=0; i<N; i++) {
			boolean isdown = false;
			int l = 1;
			int diff = 0;
			for(int j=1; j<N; j++) {
				diff = diffH(map[j-1][i], map[j][i]);
				if(Math.abs(diff)>1) break;
				if(diff == 0) {
					l++;
				} else {
					// 상승
					if(diff < 0) {
						// 한번 하강했으면 l의 두배의 길이가 필요로 한다.
						if(isdown) if(l < 2*L) break;
						if(l < L) break;
						isdown = false;
					}
					// 하강
					else {
						isdown = true;
						int tempL = 0;
						for(int k=0; k<L; k++) {
							if(j+k == N) break;
							if(map[j+k][i] == map[j][i]) {
								tempL++;
							}
						}
						if(tempL < L) break;
					}
					if(j!=N-1) l=1;
				}
				if(j==N-1) {
					if(l<L) break;
					result++;
				} 
			}
		}
		return result;
	}
	//1. 높이 차이 함수
	public static Integer diffH (int a, int b) {
		return a-b;
	}

}

dmstjddkd 5년 전 0

혹시 해결 하셨나요?

상승 시 break만 하셔서 문제가 생기신 것 같아요. 62라인 이나 104라인에서 가능한 길도 막아버립니다.

변수 선언 까지 정확하게 4줄 수정하고 2줄 추가해서 정답 받았어요.

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

문제

문제

출처

ICPC

질문드립니다 (틀렸습니다)

jin3670 5년 전 0

dmstjddkd 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말