[DP] 백준 문제 풀이 - 11726 2xN 타일링

2022. 6. 6. 23:08· PS 연습
목차
  1. 👩🏻‍💻 문제링크
  2.  
  3. ✍️ 아이디어

👩🏻‍💻 문제링크

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

 

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

 

✍️ 아이디어

1. 문제 이해

  • 문제를 해석하던 도중 단순화 해보니까 n을 1과 2의 합으로 나타낼수 있는 경우의 수였다
  • 그리고 n을 1부터 6까지 나열하여 이게 피보나치 수열과 같은 형태라는것을 알게되었다

-> 하지만 이것이 왜 피보나치 수열과 같은 형태가 나오는지는 이해하지 못했다

 

2. 점화식 : 직접 써보면 나옴 = 피보나치 수열

 

✍️소스코드

  •  (A + B) % M =  (A%M + B%M) % M 이거시 성립한다 -> 이거 안쓰면 오버플로우 생김
#include <iostream>	
using namespace std;
long long result[1001];

int main()
{
	int n; cin>>n;
	result[1]=1;
	result[2]=2;
	for(int i = 3; i<=n; i++)
	{
		result[i]=((result[i-1]%10007)+(result[i-2]%10007))%10007;
	}
	cout<<result[n]<<'\n';
}

 

✍️피드백

피보나치 수열과 같은 형태가 나오는 이유 :

가장 오른쪽에 타일을 놓는 경우의 수는 2가지가 있는데...각각의 경우의 수는 result(i-1)과 result(i-2)이다

체감난이도 걸린시간 참고 사용 문법
하 30min 백준 질문 코너 수학의 나눗셈 공식

 

'PS 연습' 카테고리의 다른 글

[DP] 백준 문제 풀이 - 11052 카드 구매하기  (0) 2022.06.25
[DP] 백준 문제 풀이 - 15990 1,2,3 더하기 5  (0) 2022.06.06
[백준] 백준 문제 풀이 - 1918 후위 표기법  (0) 2022.05.21
[PS 풀이] 백준 문제 풀이 - 17298 오큰수  (0) 2022.05.20
[백준] 백준 문제 풀이 - 11724 연결요소의 갯수  (0) 2022.05.11
  1. 👩🏻‍💻 문제링크
  2.  
  3. ✍️ 아이디어
'PS 연습' 카테고리의 다른 글
  • [DP] 백준 문제 풀이 - 11052 카드 구매하기
  • [DP] 백준 문제 풀이 - 15990 1,2,3 더하기 5
  • [백준] 백준 문제 풀이 - 1918 후위 표기법
  • [PS 풀이] 백준 문제 풀이 - 17298 오큰수
생선묵김치찌개
생선묵김치찌개
생선묵김치찌개
준혁's 코딩 연구기록
생선묵김치찌개
전체
오늘
어제
  • 분류 전체보기 (96)
    • Java (5)
    • Spring Boot (3)
    • 자료구조 (8)
    • 네트워크 (4)
    • 데이터베이스 (4)
    • 기술적 고민 (17)
      • Side Match (13)
      • 자리나따 (4)
    • C++ (3)
    • Algorithm (4)
    • PS 연습 (38)
    • 잡동사니 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • DN
  • 백준
  • 파일 업로드
  • 완전탐색
  • 단순 연결 리스트
  • backend
  • 백준 골드
  • aws rds
  • dp
  • 예외처리
  • sentry
  • 재귀
  • 스택
  • 이진트리
  • 열혈 자료구조
  • 브루트 포스
  • 알고리즘
  • CPP
  • open api
  • 원형 연결 리스트
  • 스프링
  • 트리
  • 수식트리
  • 큐
  • 양방향 연결 리스트
  • 자료구조
  • ㄱ
  • Stream
  • 배열 리스트
  • 해커톤

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
생선묵김치찌개
[DP] 백준 문제 풀이 - 11726 2xN 타일링
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.