📌 문제 링크
https://www.acmicpc.net/problem/1904
📌 문제 탐색하기
- 타일이 00, 1이 있다 이때 만들 수 있는 모든 가짓수를 세서 15746으로 나눈 나머지를 출력해라
시간복잡도
- O(n)
알고리즘 선택
- DP
📌 코드 설계하기
- 문제의
input
을 숫자로 변환합니다. arr
에 값을 넣어 초기화해줍니다.- 문제 참조) N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다.
input
이 2보다 같거나 작다면arr[input]
의 값을 출력합니다.- 그렇지 않다면
arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
으로arr
에 값을 할당합니다. arr[input]
으로 가짓수를 출력합니다.
📌 시도 회차 수정 사항 (Optional)
1회차
- 정말 바보같이
arr[i] = arr[i - 1] + arr[i - 2] % 15746;
이렇게 작성했다.. 왜 시작하자마자 틀리게 나오는거지? 했다가 급하게 괄호를 넣게 되었다...🤦🏻♀️
📌 기억해야 할 부분
- JavaScript의 배열은 정적 크기가 아니라 동적 크기
arr[i] = 값;
코드를 실행하면, i번째 인덱스가 아직 존재하지 않더라도, 자동으로 배열 크기를 확장하여 i번째 위치에 값을 저장- 예를 들어, i = 3일 때
arr[3] = arr[2] + arr[1]
을 할당하면 arr 배열이 [0, 1, 2, 3]처럼 확장됩니다.
📌 정답 코드
//https://www.acmicpc.net/problem/1904
export {};
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const input = Number(fs.readFileSync(filePath));
const arr = [0, 1, 2];
if (input <= 2) {
console.log(arr[input]);
} else {
for (let i = 3; i <= input; i++) {
arr[i] = (arr[i - 1] + arr[i - 2]) % 15746;
console.log(arr);
}
console.log(arr[input]);
}
'코딩 > 알고리즘' 카테고리의 다른 글
백준) 2417 - 정수 제곱근 JS (0) | 2024.11.24 |
---|---|
백준) 1920 - 수 찾기 JS (0) | 2024.11.23 |
백준) 2747 - 피보나치 수 JS (0) | 2024.11.21 |
백준) 10815 - 숫자 카드 JS (0) | 2024.11.20 |
백준) 7785 - 회사에 있는 사람 JS (0) | 2024.11.19 |