백준] 2133 : 타일 채우기

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

2133번: 타일 채우기

 

 

 

접근 방법

 3 * N 크기의 벽과 2 * 1, 1 * 2타일은 아래와 같이 생겼습니다.

이제 타일을 채워보겠습니다.


만약 N이 2이라면
3 * 2 크기의 벽은 오른쪽과 같은 타일의 3가지 경우로 채울 수 있습니다.
따라서 이 때 얻을 수 있는 점화식은 dp[n] = dp[n - 2] * 3입니다.

그리고 N이 3이라면
각각 색칠된 타일로 배열 시에는 벽을 채우지 못합니다.
따라서 N이 홀수일 때는 벽을 채우지 못하게 됩니다.

마지막으로 N이 6일 때,
채울 수 있는 타일은 3 * 2 크기의 벽에서 만들었던 타일의 배열을 활용할 수 있습니다.

총 11가지의 경우의 수가 나오는데, 여기서는 새로운 형태의 타일이 추가됩니다.

이렇게 N이 8, 10, 12... 로 짝수일 때 새로운 형태의 타일이 추가되므로
계산된 값에 새로운 타일을 추가해줘야 합니다.

dp[n] += dp[n - N] * 2 (이 때, N은 짝수)

 

 

처음 코드

: 초기화 안 해줘서 틀림

#include <iostream>
using namespace std;

int dp[31];

int main() {
	
	int N;
	
	cin >> N;
	
	dp[0] = 1;
	dp[1] = 1;
	
	for(int i = 2; i <= N; i++){
		
		dp[i] = dp[i - 2] * 3;
		for(int j = 4; j <= N; j+=2){
			dp[i] += dp[i - j] *2;
		}
	}
	
	cout << dp[N];
	
	return 0;
}

 

두 번째 코드

#include <iostream>
using namespace std;

int dp[31];

int main() {
	
	int N;
	
	cin >> N;
	
	dp[0] = 1; // 초기화
	dp[2] = 3;
	
	for(int i = 4; i <= N; i++){
		
		dp[i] = dp[i - 2] * 3;
		for(int j = 4; j <= i; j+=2){ // j는 i까지만
			dp[i] += dp[i - j] *2;
		}
	}
	
	cout << dp[N];
	
	return 0;
}

 

 

 

정답 코드

#include <iostream>
using namespace std;

int dp[31];

int main() {
	
	int N;
	
	cin >> N;
	
	dp[0] = 1;
	dp[2] = 3;
	
	for(int i = 4; i <= N; i++){
		
		dp[i] = dp[i - 2] * 3;
		for(int j = 4; j <= i; j+=2){
			dp[i] += dp[i - j] *2;
		}
	}
	
	cout << dp[N];
	
	return 0;
}

 

 

 

 

참고한 블로그

[백준(baekjoon) 2133] 타일 채우기

[알고리즘 문제] 백준2133 - 타일 채우기