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
- 동적계획법
- 자류구조
- 1931
- 11047
- 1236
- Async/Await
- 1568
- 호이스팅
- 함수 이놈
- event loop
- 백준
- 유사배열
- 11399
- 1543
- setTiemOut
- 렉시컬 스코프
- 함수 parmater
- html5
- 배열같은배열아닌너
- 9461
- 2667
- javascript
- 1904
- 함수 선언문
- 1302
- 비동기처리
- 탐욕 알고리즘
- 함수 arguments
- 1668
- baekjoon
Archives
- Today
- Total
두치의 개발공부
BaekJoon_9461 (파도반 수열) 본문
문제 풀이
N은1 부터 차근차근히 그림을 그려나가 보면 점화식을 금방 발견할 수 있다.
N | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
정삼각형 변의 길이 | 1 | 1 | 1 | 2 | 2 | 3 | 4 |
점화식 : dp[n] = dp[i-1] + dp[i-5]
초기값 : dp[1] = 1, dp[2] = 1, dp[3] = 1, dp[4] = 2, dp[5] = 2
코드
const answer = ([...number]) => {
const arr = number.map(data => Number(data))
const order = arr[0];
let dp = [];
for (let index = 1; index <= order; index++) {
dp = Array.from({ length: arr[index] + 1 }, () => 0);
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
dp[4] = 2;
dp[5] = 2;
for (let index = 6; index < dp.length; index++) {
dp[index] = dp[index - 1] + dp[index - 5];
}
console.log(dp[arr[index]])
}
};
const input = [];
require("readline")
.createInterface(process.stdin, process.stdout)
.on("line", (line) => {
input.push(line);
})
.on("close", () => {
// console.log(input)
answer(input);
process.exit();
});
// https://www.acmicpc.net/problem/9461
// 다이내믹 프로그래밍은 점화식을 찾아서 리스트화 하는게 핵심
코드는 깃헙에서도 확인 가능합니다 :)
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_1904(01타일) (0) | 2022.04.28 |
BaekJoon_1003(피보나치 함수) (0) | 2022.04.28 |