Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- 비동기처리
- 함수 이놈
- 렉시컬 스코프
- baekjoon
- 함수 arguments
- 동적계획법
- 호이스팅
- 백준
- setTiemOut
- 1668
- html5
- Async/Await
- 9461
- 배열같은배열아닌너
- 자류구조
- 1568
- 11047
- 함수 parmater
- 유사배열
- 함수 선언문
- javascript
- 11399
- 1904
- event loop
- 탐욕 알고리즘
- 2667
- 1302
- 1931
- 1236
- 1543
Archives
- Today
- Total
두치의 개발공부
BaekJoon_1904(01타일) 본문
짖궂은 동주 때문에 0을 낱개로 사용할 수 없게 되었다... (1와 00 만 사용가능)
N이 1 일 때부터 경우의 수를 보면 금방 규칙을 파악할 수 있다.
N = 1 일 때 , 1 => 1개
N = 2 일 때, 11 / 00 => 2개
N = 3 일 때, 100 / 001 / 111 => 3개
N = 4 일 때, 1111 / 1001 / 0000 / 0011 / 1100 => 5개
N = 5 일 때, 11111 / 00111 / 10011 / 10011 / 11001 / 11100 / 00001 / 00100 => 8개
전형적인 피보나치 수열의 형태를 보이고 있다.
점화식을 새워보면
dp(n) = dp(n-1) + dp(n-2)
초기값으로는
dp[0] = 1
dp[1] = 2 로 설정하면 dp[3]부터 반복문을 통해서 얻을 수 있다.
코드
const answer = (number) => {
const arr = Array.from({length : number + 1}, () => 0);
arr[1] = 1;
arr[2] = 2;
for (let index = 3; index < arr.length; index++) {
arr[index] = (arr[index-1] + arr[index-2]) % 15746;
}
const result = arr[number];
console.log(result);
}
const input = [];
require("readline")
.createInterface(process.stdin, process.stdout)
.on("line", (line) => {
input.push(line);
})
.on("close", () => {
// console.log(input)
answer(Number(input));
process.exit();
});
코드는 깃헙에서도 확인할 수 있습니다 :)
https://github.com/duduchi/Algorithm/tree/main/Dynamic
'알고리즘' 카테고리의 다른 글
BaekJoon_11399(ATM) (0) | 2022.05.06 |
---|---|
BaekJoon_1932(정수 삼각형) (0) | 2022.05.03 |
BaekJoon_1149(RGB 거리) (0) | 2022.05.03 |
BaekJoon_9461 (파도반 수열) (0) | 2022.04.30 |
BaekJoon_1003(피보나치 함수) (0) | 2022.04.28 |