Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
Tags
- dp
- 2018
- dfs
- find
- 문자열
- 이런게4문제
- 백트래킹
- 삼성SW테스트
- Set
- Sort
- 시뮬레이션
- C++
- BFS
- 코딩스킬
- 코딩테스트
- 레벨3
- 삼성
- STL
- substr
- 레벨2
- 백준
- 삼성SW역량테스트
- priority_queue
- 완전탐색
- 프로그래머스
- 브루트포스
- 모의SW역량테스트
- swea
- Map
- KAKAO
Archives
- Today
- Total
-
[프로그래머스_레벨 3] 2 x n 타일링 본문
https://programmers.co.kr/learn/courses/30/lessons/12900
코딩테스트 연습 - 2 x n 타일링 | 프로그래머스
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 s
programmers.co.kr
백준에 동일한 문제가 있다.
이 문제는 dp로 풀 수 있는데 n=1, n=2, ...일 때를 해보면 경우의 수가 피보나치 수열을 이루고 있음을 알 수 있다.
이렇게 점화식이 간단히 나오는 경우 쉽게 풀 수 있지만 좀 더 어려운 dp문제는 점화식을 찾는데 주력해야 한다. 그 뒤에는 쉽게 dp문제를 풀 수 있다.
피보나치 수열은 dp[n] = dp[n-1] + dp[n-2] (n은 3이상 자연수) 의 점화식을 가지므로 그대로 구현해주면 된다.
유의할 점은 연산 후 mod로 나눈 나머지를 저장해줘야 한다는 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <string>
#include <vector>
#define mod 1000000007
using namespace std;
int dp[60001];
int solution(int n) {
dp[1] = 1; dp[2] = 2;
if(n <= 2) return dp[n];
for(int i=3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
dp[i] %= mod;
}
return dp[n];
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
'1-4. 프로그래머스' 카테고리의 다른 글
[프로그래머스_레벨 3] 오픈채팅방(2019 KAKAO BLIND RECRUIT.) (0) | 2020.02.11 |
---|---|
[프로그래머스_레벨 3] 여행 경로 (DFS) (0) | 2020.02.10 |
[프로그래머스] 레벨 3 - 네트워크 (0) | 2020.02.09 |
[프로그래머스] 레벨 2 - 타겟 넘버 (0) | 2020.02.07 |
[프로그래머스] 레벨 2 - 카펫 (0) | 2020.02.07 |
Comments