10장은 Dynamic Programming(동적계획법)에 대한 문제들이다.
문제
철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.
그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?
[입력설명]
첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다.
[출력설명]
첫 번째 줄에 올라가는 방법의 수를 출력합니다.
입력예제 1
7
출력예제 1
21
문제 풀이
예습 이론
동적계획법(Dynamic programming) 은 문제가 어려워서 한번에 푸는 것이 불가능할 때, 쪼개서 작은단위로 문제를 풀다가 큰 단위로 넓혀가며 문제를 풀어나가는 방법이다. 배열을 사용해서 풀 수 있다. (문제에서는 dy)
동적계획법은 관계를 통해 문제를 해결한다(점화식 관계)
어려운 문제가 많기 때문에, 많이 풀어봐야한다.
코드
- 동적계획법을 사용해서 푸는 문제이다. 동적계획법에서 중요한 배열을 만들어준다.(dy배열)
dy[i]는 i계단까지 갈 수 있는 방법의 수를 저장한다. - 규칙을 찾는것이 중요하다!
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n){
let answer;
let dy=Array.from({length:n+1}, ()=>0);
dy[1]=1;
dy[2]=2;
//3번째 계단부터 구함
for(let i=3; i<=n; i++){
dy[i]=dy[i-2]+dy[i-1];
}
answer=dy[n];
return answer;
}
console.log(solution(7));
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/18