글 읽기 - 여기서 무엇을 손봐야 할까요?

citizen 6년 전 0

일단 당연히 dp를 사용하였고

무조건 최단거리로만 가야 한다고 조건이 주어졌으니

최단거리 알고리즘에다가 res라는 3차원 배열을 도입했습니다.

res[x][y][1] = -1이면 (x,y)에서 (x+1, y)로 갈수 없으며

res[x][y][0] = -1이면 (x,y)에서 (x, y+1)로 갈수 없도록

제한을 두었습니다.

반례를 발견하시거나 고쳐야 할 부분을 지적해주셨으면 합니다.

import java.util.*;
import java.awt.List;
import java.io.*;
import java.math.*;
 
public class Main{
    public static BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = 
            new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static int h, w;
    public static int[][] dp;
    public static int[][][] res; // 0이 위 1가 오
    
    public static void main(String args[]) throws IOException{
        Scanner sc = new Scanner(System.in);
        String[] vals = (br.readLine()).split(" ");
        w = Integer.parseInt(vals[0]);
        h = Integer.parseInt(vals[1]);
        dp = new int[h+1][w+1];
        res = new int[h+1][w+1][2];
        dp[0][0] = 1;
        int K = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int x1, x2, y1, y2;
        for(int i = 0; i < K; i++){
        	st = new StringTokenizer(br.readLine(), " ");
        	x1 = Integer.parseInt(st.nextToken());
        	y1 = Integer.parseInt(st.nextToken());
        	x2 = Integer.parseInt(st.nextToken());
        	y2 = Integer.parseInt(st.nextToken());
        	if(x1 == x2){
        		if(y1 > y2) res[y2][x1][0] = -1;
        		else res[y1][x1][0] = -1;
        	}else{
        		if(x1 > x2) res[y1][x2][1] = -1;
        		else res[y1][x1][1] = -1;
        	}
        }
        for(int i = 0; i <= h; i++){
        	for(int j = 0; j <= w; j++){
            	if(i == 0 && j == 0) continue;
            	else if(i != 0 && j == 0){
            		if(res[i-1][j][0] != -1) dp[i][j] = dp[i-1][j];
            	}else if(i == 0 && j != 0){
            		if(res[i][j-1][1] != -1) dp[i][j] = dp[i][j-1];
            	}else{
            		if(res[i-1][j][0] != -1) dp[i][j] += dp[i-1][j];
            		if(res[i][j-1][1] != -1) dp[i][j] += dp[i][j-1];
            	}
            }
        }
        bw.write(dp[h][w]+"\n");
        bw.close();
    }
}

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

문제

문제

출처

ICPC

여기서 무엇을 손봐야 할까요?

citizen 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말