BOJ : 11726 2xn 타일링.
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
어떻게 풀 것인가?
과정을 생략하고 코드를 보고싶은 분은 맨 아래로
접근 방법 : Dynamic Programming
보자마자 생각했다. Dynamic Programming.
2 n 의 타일을 만드는 갯수는 2 (n-1) 또는 2 * (n-2)의 갯수와 관계가 있을것이 분명하다!
이 관계를 찾아야 한다.
기본 입출력 정의
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin>>t;
int dp[t+1];
dp[1] = 1;
dp[2] = 2;
}
t를 입력받아 dp배열을 생성하고 dp[1] = 1, dp[2] = 2로 초기화 한다.
💢 타일이 중복과 추가가 되는구나💢
처음에는 n번째 타일의 양쪽에 세로 타일을 붙이는 것을 생각했다.
근데 중복되는 타일과 추가되는 타일이 생긴다. 중복되는 타일과 추가되는 타일에 대한 규칙을 찾기 어려웠다...
타일을 양쪽에 붙인다는 규칙으로는 규칙성이 생기지 않는 것 같다. → 타일을 한방향(오른쪽)으로 붙이자!
한방향으로 타일 붙이기
그러면 한방향으로 타일을 2개(세로+세로 / 가로 + 가로)를 붙일 것인지? 혹은 타일을 1개를 붙일 것인지 생각해야 했다.
n번째 타일은 n-2번째 타일에서 (세로+세로)타일을 붙이거나 (가로+가로)타일을 붙이는 것이다.
➕
n번째 타일은 n-1번째 타일에서 (세로) 타일을 붙이는 것이다.
그림에서 보이는 것 처럼 중복이 발생한다.
중복은 어떻게 이루어지나?
중복이 되는 타일만 제거를 하면 될 것 같다.
중복이 어떻게 생기는지 알아보기 위해서 다 그려봤다.
그리다 보니 드는 생각
세로 타일로 끝나는 타일만 ➕ 맨 오른쪽 세로타일이 2개 이상인 타일
만 중복이 일어난다!
💥 결론 : n-2번째에서 세로타일을 두개 붙이는 타일은 중복이 일어난다!
그렇다.
그럼 dp식을 완성해보자.
dp[n] = dp[n-2] * 2 (n-2 타일에 세로 + 세로, 가로 + 가로 붙이기)
➕ dp[n-1] (n-1 타일에 세로 붙이기)
➖ dp[n-2] (n-2 타일에 세로 + 세로를 붙이는 건 중복된다.)
dp[n] = dp[n-2] + dp[n-1]
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin>>t;
int dp[t+1];
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<t+1;i++){
dp[i] = dp[i-2] + dp[i-1];
}
cout<<dp[t];
}
예제입력은 잘 돌아간다.
하지만 섣부르게 제출하면 바로 틀립니다.....
😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭
네 그렇습니다. 어쩐지 바로 그냥 틀려버리더라
바로 틀린다 → 큰 수의 입력에서 틀린다!
제출하기 전에 Check할 것!
- 입력, 계산, 출력값이 int의 자료를 넘어가는가? (int = 2,147,483,648)
- 작은 값의 입력을 잘 해결하는가? (1, 2 정도의 입력을 해보자)
- 불필요한 log들 전부 지우고 제출해봅시.
- ➕ 문제에서 추가로 요구하는 요구사항은 없는가?
코드를 수정해준다.
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin>>t;
int dp[t+1];
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<t+1;i++){
dp[i] = (dp[i-2] + dp[i-1]) % 10007;
// dp[i] = dp[i-2] + dp[i-1];
}
cout<<dp[t];
}
👨💻 재도전! 🚙
과 함께 성공했습니다 :)
🌕 FULL CODE ⛽
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin>>t;
int dp[t+1];
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<t+1;i++){
dp[i] = (dp[i-2] + dp[i-1]) % 10007;
// dp[i] = dp[i-2] + dp[i-1];
}
cout<<dp[t];
}
🤜 FeedBack 🤛
- 채점 시간이 엄청 오래 걸리던데 왜그런걸까..?
- 문제 제대로 읽자 ^^......ㅜㅜㅜㅜㅜ
Author And Source
이 문제에 관하여(BOJ : 11726 2xn 타일링.), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@boong_u/BOJ-11726-2xn-타일링
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin>>t;
int dp[t+1];
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<t+1;i++){
dp[i] = (dp[i-2] + dp[i-1]) % 10007;
// dp[i] = dp[i-2] + dp[i-1];
}
cout<<dp[t];
}
- 채점 시간이 엄청 오래 걸리던데 왜그런걸까..?
- 문제 제대로 읽자 ^^......ㅜㅜㅜㅜㅜ
Author And Source
이 문제에 관하여(BOJ : 11726 2xn 타일링.), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@boong_u/BOJ-11726-2xn-타일링저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)