PS) 백준 1309, 10164번 (동물원, 격자상의 경로)

오늘은 토요일이라 안하려 하다가 양심에 찔려서 몇문제라도 풀어본다..

 

1309번 동물원

 

처음에 생각을 잘못해서,,,,,,,,, 삽질한 문제이다.

3차원 배열을 선언해서, i번째 열의, n행의 방의 동물의 여부에 따라서 계산을 해주었더니 구현이 되지 않았다.

깊게 생각하지 않고 가볍게 생각해보니 그렇게 어렵게 들어가지 않아도 되는 문제였다...

 

i번째 열에서 올 수 있는 동물의 경우는 

1)  O    2)    X    3)    X

     X          O          X

이 세가지이다. 따라서 dp를 2차원으로 구현한다. dp[n][3] => n열에서 올 수 있는 경우는 세가지 경우

첫번째 경우는 이전 열에서 2,3번의 경우일 때 가능

두번째 경우는 이전 열에서 1,3번의 경우일 때 가능

세번째 경우는 이전 열에서 1,2,3번의 경우일 때 가능

 

그림으로 그려 생각해주면 바로 풀리는 문제였다.... 왜 처음 봤을 때 생각 못한걸까 흑

 

다른 분들 풀이를 참고하니, 각 경우에 따라 수를 나열해보아 규칙을 찾으면

dp[i]=dp[i-1]*2 + dp[i-2]의 점화식도 가능하다고 한다. => 왜 가능한지 이해 못함

 

#include<stdio.h>
int dp[100005][3];
#define MOD 9901;

int main() {
	int n; scanf("%d", &n);
	dp[1][1] = 1; dp[1][2] = 1; dp[1][3] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
		dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % MOD;
		dp[i][3] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % MOD;
	}
	int sum = dp[n][1] + dp[n][2] + dp[n][3];
	printf("%d", sum  % 9901);
}

 

 

 

 

10164번 격자상의 경로

 

별로 안어려웠당

다만 고려해야 할 부분이 많았음!

 

#include<stdio.h>
int dp[17][17];

int main() {
	int n, m, k; scanf("%d%d%d", &n, &m, &k);
	int row, col;
	if (k % m == 0) col = m;
	else col = k % m;	
	if (k % m == 0) row = k/m;
	else row = k / m + 1;
	for (int i = 1; i <= n; i++) dp[i][1] = 1;
	for (int i = 1; i <= m; i++) dp[1][i] = 1; 
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= m; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	if (k == 0) printf("%d", dp[n][m]);
	else {
		long long sum = dp[row][col] * dp[n - row + 1][m - col + 1];
		printf("%lld", sum);
	}
}