boj, 백준 ) 17070 파이프 옮기기1 (C, C++)

1. 문제 링크

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

2. 문제 개요

벽을 피해 3가지 모양의 파이프를 사용하여 왼쪽 위에서 오른쪽 밑까지 갈 수 있는 방법 수 세기.

 

3. 문제 힌트!!

    DP를 이용하여 풀어봤음.

3가지 경우의 수를 고려해서 풀 것.

가로 -> 가로 + 대각선

세로 -> 세로 + 대각선

대각선 -> 가로 + 세로 + 대각선

 

4. 문제 풀이

 dp[3][n][m] 으로 정의, [0][n][m]은 가로 모양을 놓을 수 있는 경우의 수

[1][n][m]은 세로, [2][n][m]은 대각선으로 정의하였다.

(3) 번에 있는 내용을 그대로 적용하여 풀었다.

 

5. 코드

#include <stdio.h>
#include<algorithm>
using namespace std;

int dp[3][17][17];
//0 -> ㅡ 1-> ㅣ 2-> /
int map[17][17];

int main(void)
{
	int n;
	scanf("%d",&n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		scanf("%d", &map[i][j]);

	for (int j = 2; j <= n; j++)
	{
		if (map[1][j] == 1)	break;
		dp[0][1][j] = 1;
	}
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] != 1)
			{
				dp[0][i][j] = dp[0][i][j - 1] + dp[2][i][j - 1];
				dp[1][i][j] = dp[1][i - 1][j] + dp[2][i - 1][j];
				if (map[i - 1][j] != 1 && map[i][j - 1] != 1)
					dp[2][i][j] = dp[0][i- 1][j - 1] + dp[1][i - 1][j - 1] + dp[2][i - 1][j - 1];
			}
		}
	printf("%d", dp[0][n][n] + dp[1][n][n] + dp[2][n][n]);
	return 0;
}

 

지적, 댓글 언제나 환영입니다~