[백준 31910] 이진수 격자 (C++)

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

문제

---

각 칸에 0 또는 1이 적혀 있는 N×N격자가 있다. 인선이는 1행 1열에서 출발해 N행 N열까지 이동하는데, 오른쪽(열 번호가 증가하는 방향) 또는 아래(행 번호가 증가하는 방향)로만 한 칸씩 이동할 수 있다. 인선이는 어떤 칸에 방문할 때마다 그 칸에 적힌 문자를 자신이 갖고 있는 문자열의 뒷부분에 덧붙인다. 예를 들어, 주어진 그림에서 인선이가 1행 1열에서 출발하여 순서대로 오른쪽, 아래, 오른쪽으로 한 칸씩 이동한다면 인선이가 가진 문자열은 1101이다.

N행 N열에 도착하면 인선이는 자신이 갖고 있는 문자열을 이진수로 해석한 값 M을 계산한다. 예를 들어, 인선이가 가진 문자열이 1101일 경우 M=13이다. 인선이가 계산하게 될 M의 최댓값을 구하시오.

입력

---

첫째 줄에 격자의 크기를 의미하는 정수 N이 주어진다. (2 ≤ N ≤ 30)

둘째 줄부터 N개의 줄에 걸쳐 한 줄에 N개의 정수가 공백으로 구분되어 주어진다. 이 정수는 반드시 0 또는 1이다. (i+1)번째 줄에 주어진 j번째 수는 i행 j열에 적힌 격자의 칸에 적힌 수를 의미한다.

출력

---

 M의 최댓값을 출력한다. 정답이 32비트 정수 범위를 넘을 수 있음에 주의하시오.

 

서브태스크

---

 

번호	배점	제한
1	20	N ≤ 5
2	30	행 번호와 열 번호가 서로 다른 칸에는 모두 0이 적혀 있다.
3	50	추가 제약 조건이 없다.

 

문제 풀이

---

dp 문제.

 

한 칸을 이동할 때마다 만들어진 문자열 뒤에 도착한 칸의 문자를 붙이게 된다. 이를 2진법으로 변환하면 왼쪽으로 한 칸shift 이동(혹은 2배)하고 도착한 칸의 문자를 더한 것과 같다. 각 칸에 주어질 수 있는 값은 칸의 왼쪽에서부터 오거나, 위쪽에서부터 오는 것이다. 두 방법 모두 이동하며 2배가 되고 해당 칸의 문자를 더하는 방식이므로, 이전 칸의 값이 큰 쪽이 더 큰 값을 얻을 수 있다. 따라서 2차원 dp 배열을 선언한 후, [i][j]칸을 채울 때 [i-1][j]과 [i][j-1]을 비교하여 더 큰 값에 2를 곱하고, [i][j]를 더하면 해당 칸까지 도달하는데 얻어지는 최댓값을 구할 수 있다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;

long long pow(int x, int y)
{
	if (y == 0)
	{
		return 1;
	}
	else
	{
		long long answer = x;
		for (int i = 1; i < y; i++)
		{
			answer *= x;
		}
		return answer;
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int** map = new int*[N];
	long long** dp = new long long*[N];
	for (int i = 0; i < N; i++)
	{
		map[i] = new int[N];
		dp[i] = new long long[N];
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
			dp[i][j] = 0;
		}
	}
	dp[0][0] = map[0][0];
	for (int i = 1; i < N; i++)
	{
		dp[i][0] = dp[i - 1][0] * 2 + map[i][0];
		dp[0][i] = dp[0][i - 1] * 2  + map[0][i];
	}
	for (int i = 1; i < N; i++)
	{
		for (int j = 1; j < N; j++)
		{
			dp[i][j] = 2 * max(dp[i - 1][j], dp[i][j-1]) + map[i][j];
		}
	}
	cout << dp[N - 1][N - 1] << "\n";
	return 0;
}