똥대

1. 언어 : JAVA

1563번: 개근상

 

www.acmicpc.net

2. 난이도 : Gold 4

3. 풀이

일단 가장 중요한건 이 문제가 DP라는 걸 알아야한다는 것이다.

(본인은 Memoization을 사용하긴했다.)

DP를 위해서 DP 배열의 정의를 먼저 내려야하는데, 출석을 몇일했는지는 의미가 없고, 우리는 

결석을 몇번했는지, 지각은 몇번했는지, 또 그 결석이 연속됐는지가 중요하다.

그렇기 때문에 DP[날짜][지각횟수][결석횟수]

로 잡아주고 DP[1001][3][4] 로 선언을 해주게 된다. (N<1001, 지각 최대 2번, 결석 최대 3번)

그래서 우리는 재귀를 이용할 건데.

1. 출석했을때 : DP[date+1][late][abs]

2. 지각했을때 : DP[date+1][late+1][abs]

3. 결석했을때 : DP[date+1][late][abs+1]

로 케이스를 나눌 수 있다. 모~든 케이스를 탐색하도록 재귀를 만들고 기저사례를 만들고,

Memoization 코드를 넣으면 끝이다.

4. 소스코드

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

public class Main {
	public static int N = 0;
	public static long [][][] dp = null;
	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		
		dp =  new long[1001][3][4];
		for(int i=0; i<=1000; i++) {
			for(int j=0; j<=2; j++) {
				for(int z=0; z<=3; z++) {
					dp[i][j][z] = -1;
				}
			}
		}
		
		long result = search(1, 0, 0) + search(1, 1, 0) + search(1, 0, 1); 
		System.out.println(result%1000000);
	}
	
	public static long search(int day, int late, int abs) {
		if(dp[day][late][abs] != -1) {
			return dp[day][late][abs]%1000000;
		}
		
		if(late == 2 || abs == 3) {
			dp[day][late][abs] = 0;
			return 0;
		}
		
		if(N == day) {
			dp[day][late][abs] = 1;
			return 1;
		}

		long result = 0; 
		result += (search(day+1, late+1, 0) + search(day+1, late, abs+1) + search(day+1, late, 0)) % 1000000;
		
		dp[day][late][abs] = result;
		
		return result%1000000;
	}
}

1. 언어 : JAVA

1577번: 도로의 개수

 

www.acmicpc.net

2. 난이도 : Gold 4

3. 풀이

아니.. 뭐 이렇게 많이 틀렸냐. 틀린 이유를 한번 살펴보자. 

처음에 map을 [M+1][N+1] 크기만큼 생성하고, 다리를 1로 두었다. 

예를들어 저기서 못지나가는 다리가 진한것이라고 가정하면

1 1 1 0 0

1 0 1 0 0

0 0 0 0 0

0 0 0 0 0

으로 체크를 해주었다. 근데 여기서 심각한 오류가 있는게...... 처기에 처음 1 1 1이 나오는 곳이 실제로는 못지나가는 영역이 아닌데 못지나가게 된다는 것이다. 그래서.. 다른 방법을 찾았는데

[M+1][N+1][2] 으로 3차원으로 해서 [M+1][N+1][0] 은 가로로 공사중인곳 [M+1][N+1][1] 은 세로로 공사중인 곳을 하여 체크를 하려고했지만 소스가 더러워져서 그냥 포기했다.

그래서 마지막으로 생각해 낸게. 그냥 [M*2+1][N*2+1] 로 선언을 하여 중간중간마다 공사의 유무를 적어논 것이다. 그러면 결국 이렇게 될 것이다.

0 1 0 0 0 0 0 0 0 

1 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 

이렇게 2칸 사이사이에는 공사의 유무가 1로 저장될 것이다.

그리고 생각해야할게 이 방법을 어떻게 풀까.. 고민한게 있는데 문제를 보다보니 뭔가 중학교때 풀었던 스멜이 났다. (그때는 DP가 뭔지몰랐지만..)

그래서! DP로 풀기로하였다. 그때의 기억을 떠올리며.

초기 나를 기준으로 가로와 세로의 값을 1또는 0으로 초기화 한다. 

		// 가로
		for(int i=2; i<=N*2; i+=2) {
			if(block[0][i-1] == 1) {
				break;
			}
			else {
				dp[0][i] = 1;
			}
		}
		
		// 세로
		for(int i=2; i<=M*2; i+=2) {
			if(block[i-1][0] == 1) {
				break;
			}
			else {
				dp[i][0] = 1;
			}
		}

그 다음 i=2, j=2부터 시작하여 i는 M*2까지, j는 N*2까지 진행하며 i+=2, j+=2로 진행해준다.

또한 점화식은 다음과 같다.

		for(int i=2; i<=M*2; i+=2) {
			for(int j=2; j<=N*2; j+=2) {
				if(block[i-1][j] == 0) {
					dp[i][j] += dp[i-2][j];
				}
				if(block[i][j-1] == 0) {
					dp[i][j] += dp[i][j-2];
				}
			}
		}

이렇게 해주면 [M*2][N*2]에 갈 수 있는 최단 거리가 나오게 된다.

예시를 보면 쉽다. 이러한 예제가 있다고 가정해보자.

3 3

1

0 0 0 1

그러면 결과물은 다음과 같다.

쉽게 표현하면.

0 1 1 1

0 0 0 0 

0 0 0 0 

0 0 0 0 

에서 시작을 해서 

0 1 1 1

0 1 2 3

0 1 3 6

0 1 4 10 

이렇게 끝나게 되는것이다.

본인 위치 오면 왼쪽과 위의 값을 잘 조합해서(점화식에따라) 값을 넣어주는 DP인 것이다.

4. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		long [][] dp = new long[M*2+1][N*2+1];
		long [][] block = new long[M*2+1][N*2+1];
		
		int K = Integer.parseInt(br.readLine());
		for(int k=0; k<K; k++) {
			String [] split = br.readLine().split(" ");
			int a = Integer.parseInt(split[0]);
			int b = Integer.parseInt(split[1]);
			int c = Integer.parseInt(split[2]);
			int d = Integer.parseInt(split[3]);
			
			block[b+d][a+c] = 1;
		}
		
		// 가로
		for(int i=2; i<=N*2; i+=2) {
			if(block[0][i-1] == 1) {
				break;
			}
			else {
				dp[0][i] = 1;
			}
		}
		
		// 세로
		for(int i=2; i<=M*2; i+=2) {
			if(block[i-1][0] == 1) {
				break;
			}
			else {
				dp[i][0] = 1;
			}
		}
	
		for(int i=2; i<=M*2; i+=2) {
			for(int j=2; j<=N*2; j+=2) {
				if(block[i-1][j] == 0) {
					dp[i][j] += dp[i-2][j];
				}
				if(block[i][j-1] == 0) {
					dp[i][j] += dp[i][j-2];
				}
			}
		}
		
		bw.write(dp[M*2][N*2] + "\n");
		bw.flush();
		bw.close();
	}
}