[C++] 백준 17070. 파이프 옮기기1

1. 문제

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

 

2. 아이디어

다이나믹 프로그래밍으로 풀 수 있는 문제일 것 같다.

특정 좌표를 (y, x) 라고 했을 때

파이프의 우측 좌표를 기준으로 (좌측 좌표는 생각할 필요 없다.)

 

(y, x) 에 가로로 도착할 횟수

+

(y, x) 에 세로로 도착할 횟수

+

(y, x) 에 대각선으로 도착할 횟수

 

의 합을 구하면, 해당 좌표에 도달할 수 있는 모든 경우의 수가 된다.

 

이 때, 벽에 막힐수도 있기에 예외처리에 신경쓴다.

 

3. 풀이

 

먼저 전역변수 목록이다.

tableSize는 격자의 크기

table은 격자의 정보를 입력하는 부분

 

dpRight, dpDown, dpRD 는 각각

특정 좌표에

가로로 도착하는 경우, 세로로 도착하는 경우, 대각선으로 도착하는 경우를 뜻한다.

 

예를들어

dpRight[10][10] 을 구하고 싶다면

(10, 10) 에 가로로 도착하는 경우의 수는

(10, 9) 에 대각선 상태일 때의 경우의 수와

(10, 9) 에 가로 상태일 때의 경우를 수를 더하면 된다.

 

dpDown[10][10]을 구하고 싶다면

(9, 10) 에 세로로 도착하는 경우와

(9, 10) 에 대각선으로 도착하는 경우를 더하면 된다.

 

dpRD[10][10]을 구하고 싶다면

(9, 9) 에 세로로 도착하는 경우

(9, 9) 에 가로로 도착하는 경우

(9, 9) 에 대각선으로 도착하는 경우를 더하면 된다.

 

여기에다가 벽의 경우를 생각하면 쉽게 답을 구할 수 있다.

 

 

입력

 

 

로직

이런 좌표 문제를 풀 때는

경계체크가 매우 중요합니다.

 

 

출력

 

 

결과

 

 

아래는 코드입니다.

#include <iostream>
using namespace std;


int tableSize;
char table[17][17];

int dpRight[17][17];
int dpDown[17][17];
int dpRD[17][17];

int main()
{
	/* 입력 */
	{
		cin >> tableSize;

		for (int i = 0; i < tableSize; i++)
			for (int j = 0; j < tableSize; j++)
			{
				int input;
				cin >> input;
				table[i][j] = input;
			}
	}

	/* 로직 */
	{
		/*초기화*/
		dpRight[0][1] = 1;
		
		for (int i = 0; i < tableSize; i++)
		{
			for (int j = 0; j < tableSize; j++)
			{
				if (i == 0 && j == 0) /* 예외처리 */
					continue;

				/* 가로 이동 */
				if (table[i][j] != 1 && j - 1 >= 0 && !(i==0 && j==1))
					dpRight[i][j] = dpRight[i][j - 1] + dpRD[i][j - 1];

				/* 세로 이동 */
				if (table[i][j] != 1 && i-1 >= 0)
					dpDown[i][j] = dpDown[i - 1][j] + dpRD[i - 1][j];

				/* 대각 이동 */
				if (table[i][j] != 1 && table[i - 1][j] != 1 && table[i][j - 1] != 1 && i - 1 >= 0 && j - 1 >= 0)
					dpRD[i][j] = dpRD[i - 1][j - 1] + dpDown[i - 1][j - 1] + dpRight[i - 1][j - 1];

			}
		}
	}

	/* 출력 */
	{
		cout << dpRight[tableSize - 1][tableSize - 1]
		+dpDown[tableSize - 1][tableSize - 1]
		+dpRD[tableSize - 1][tableSize - 1];
	}
}

 

 

오랜만에 DP 문제를 푸니까 헷갈리네요 ^^..

원래도 PS에 강하진 않았지만 더 약해진듯합니다.

하루에 2문제는 꼭 풀려고 합니다.