[백준/C++] 1793번. 타일링

문제

1793번: 타일링

 

 

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

이 문제의 좀 더 쉬운 버전.

---

1. 첫 번째 풀이

사고 과정

매우 단순한 형태의 DP였기에, 간단히 풀었다.

 

타일은 1x2, 2x1, 2x2가 있다. 행은 2행으로 고정이니, 열만 생각해보자.

 

1개의 열에 놓을 수 있는 타일 수는 몇 개인가? 1x2 한 개다.

2개의 열엔? 1x2 2개, 2x1 2개, 2x2 1개. 3가지 경우의 수가 있다.

 

하지만 이 중 1x2를 2개 놓는 건, 1번째 경우의 수(1개의 열에 놓는 경우)와 겹치니 제외한다.

 

그러니 타일링은 1칸 전 최댓값 + 2칸 전 최댓값 * 2가 정답이 된다.

 

이를 250칸 하면 끝

 

코드

#include <iostream>
#include <vector>

int main() {
	int t;
	std::cin >> t;

	while (t--) {
		int n;
		std::cin >> n;

		std::vector<int> dp(n + 1, 1);
		
		for (int i = 2; i <= n; ++i) {
			dp[i] = dp[i - 1] + 2 * dp[i - 2];
		}

		for (auto& i : dp) {
			std::cout << i << " ";
		}
	}
}

 

결과

 

하지만, 이 문제의 진가는 200만 넣어도 61자리 숫자가 출력되는, 큰 수의 연산이 핵심이었다.

---

2. 마지막 풀이

사고 과정

자릿수가 어마무시한 만큼, 정수로 커버할 생각은 일찌감찌 버려야 한다.

 

string 벡터로 dp를 변경하고, string 끼리의 덧셈을 구현한다.

 

string끼리 덧셈은 어떻게 구현해야 할까?

---

우선 정수는 일의 자리(뒤쪽)부터 계산하지만, 인덱스를 두 개 만들긴 귀찮았다.

 

그래서 입력받는 string a, b를 뒤집어 시작했다.

 

덧셈부 구현은 간단했다. i번째 자리(0부터 끝까지)에 대해

1. 두 char를 int로 변경(a[i] - '0' 사용)
2. 두 int를 덧셈(최대 2자리), num에 저장
3. string sum에 num % 10을 char로 변환해 추가(num % 10 + '0')
4. num / 10은 carry로 저장(int)

이를 반복하다보면 몇 가지 문제점이 발생한다.

 

• i의 마지막은 얼마인가?
  • 짧은 문자열의 사이즈가 되어야 한다. 이를 위해 항상 a가 더 길 수 있도록, a가 더 짧다면 a와 b를 swap했다.
• a와 b의 길이가 같을 때, 올림이 발생한다면?
  • 둘이 같을 때 a의 끝에 0을 추가
  • while문을 탈출했을 때, i == b.size()다. b가 4자리면 4인 상태.
  • 반복문이 끝난 후 a[i]에 carry를 더한다. (이때, 둘의 길이가 같다면 a[i] == 0이다.)
  • a의 남은 부분들을 모두 sum에, 그대로 추가한다. a가 끝날 때까지.
• 위에서 추가한 더미(0) 때문에, 올림이 발생하지 않으면 sum의 맨 앞에 0이 붙는다.
  • 리턴 전 reverse를 통해 sum을 다시 돌려놓는데, 그 전에 sum의 마지막 자리가 0이면 제거(pop_back)한다.
• 위 과정들을 통해 문자열로 정수의 덧셈을 구현할 수 있었다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

// 문자열 덧셈
std::string string_add(std::string a, std::string b) {
	std::reverse(a.begin(), a.end());
	std::reverse(b.begin(), b.end());

	// a > b, always.
	if (a.size() < b.size()) {
		std::swap(a, b);
	}

	else if (a.size() == b.size()) {
		a += '0';
	}

	int i = 0, carry = 0;
	std::string sum = "";
	for (; i < b.size(); ++i) {
		int num = (a[i] - '0') + (b[i] - '0') + carry;
		sum.push_back(num % 10 + '0');
		carry = num / 10;
	}

	a[i] += carry;

	// a가 남은 경우
	while (i < a.size()) {
		sum += a[i++];
	}

	if (sum[--i] == '0') {
		sum.pop_back();
	}

	std::reverse(sum.begin(), sum.end());

	return sum;
}

int main() {
	int n;
	while (std::cin >> n) {
		std::vector<std::string> dp(n + 1, "1");

		for (int i = 2; i <= n; ++i) {
			dp[i] = string_add(dp[i - 1], dp[i - 2]);
			dp[i] = string_add(dp[i], dp[i - 2]);
		}

		std::cout << dp[n] << " ";
	}
}

 

첫 번째 풀이에 따르면 string_multiple도 필요하지만, 2를 곱하는 연산만 있기에 add를 2번 했다.

 

결과

---

개선

사고 과정

reverse를 안 써볼까 했는데, 인덱스는 물론이고 sum에 추가할 때도 문제가 되었다. 앞에다 집어넣거나, 연산이 끝난 후 앞의 0들을 모두 지워야하는데, 둘 다 비용이 작진 않았다. 그래서 유지.

 

이후엔 딱히 건들 게 없었다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/3116458

pt58님의 코드. string을 이용하지 않아 흥미로웠지만, 이내 분석하길 포기했다.

 

간단히 훑어보자면 2진수를 이용한 건데... 아직 내가 이해하기엔 너무 어렵다.

논리회로의 덧셈기처럼 구현한 것 같은데, 왜 정보가 저장되는지... 이해할 수 없었음.

---

강평

쉬운 DP인 줄 알고 3xn 타일링 전에 몸풀기로 풀랬는데, 숫자 크기 보고 넋이 나갈... 뻔 했던 문제. 그래도 큰 수의 연산을 해볼 수 있어 유익했다. 다음엔 큰 수의 곱셈, 뺄셈, 나눗셈도 구현해봐야 겠다.