jiho_bae
Go devlog
jiho_bae
전체 방문자
오늘
어제
  • 분류 전체보기 (158)
    • JavaScript (38)
      • theory (34)
      • vanilla (4)
    • HTML & CSS (2)
    • Browser (3)
    • CS (6)
      • linux (1)
      • shell (2)
      • compiler (2)
    • DS & Algorithm (87)
      • theory (5)
      • basic (7)
      • programmers (30)
      • baekjoon (45)
    • Design Pattern (2)
    • Error (4)
    • Git & Github (4)
    • Tools (1)
    • 부트캠프 (4)
    • Small Tips (2)
    • Java (3)
    • test (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 깃 이전 커밋에서 새 브랜치 만들기
  • 대충만든자판 javascript
  • 덧칠하기 javascript
  • 자바스크립트 커링
  • 자바스크립트 비동기 마이크로 태스크 큐와 렌더링 과정
  • 계수정렬 자바스크립트
  • 백준 17406 nodeJS
  • JavaScript
  • 억억단을 외우자 javascript
  • javascript use strict
  • 1753 최단경로 javascript
  • 13460 javascript nodejs
  • 리액트 프로젝트 디버깅하기
  • 리코쳇 로봇 javascript
  • safari Date format NaN
  • 자바스크립트 sort는 왜 그모양일까
  • 외벽 점검 javascript
  • 퀵정렬 자바스크립트
  • 병합정렬 자바스크립트
  • 자바스크립트 채팅방 스크롤
  • 자바스크립트 배열의 특수함
  • 카카오 코딩테스트 양궁대회 nodeJS
  • 자바스크립트 이벤트 위임
  • fetch 취소하기
  • 자바스크립트 모듈 시스템
  • 프로그래머스 숫자카드나누기 javascript
  • 25632 소수 부르기 게임
  • 가사 검색 자바스크립트
  • safari invalid date error
  • 백준 자바스크립트 입력 템플릿

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
jiho_bae
DS & Algorithm/baekjoon

[백준] 1309번 동물원 - JavasScript(NodeJS)

[백준] 1309번 동물원 - JavasScript(NodeJS)
DS & Algorithm/baekjoon

[백준] 1309번 동물원 - JavasScript(NodeJS)

2021. 5. 16. 12:13

문제

 

1309번: 동물원

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

www.acmicpc.net


 

풀이

DP(동적 계획법) 문제이므로 DP로 접근한다.

다음 N * 2 행렬의 N번째 행만을 기준으로 생각하자.


N번째 행에 사자가 없다면 E, 사자가 있다면 I로 나타내본다.

 

N=1일 때, 경우의 수는 E=1, I=2 로 총 3이다.

 

N=2일 때, N=1의 경우의 수 각각에 2번째 행이 생성되었을 때를 생각하면
E=1로부터 E=1, I=2 생성
I=2로부터 각각 E=1, I=1이 생성되므로 총 E=2, I=2가 생성
그러므로 N=2의 경우의 수는 E=1+2, I=2+2로 총 7이다.

 

계속해서 진행하면,
N=3일 때, N=2의 경우의 수 각각에 3번째 행이 생성되므로
E=3으로부터 E=3, I=6 생성
I=4로부터 총 E=4, I=4 생성
N=3의 경우의 수는 E=3+4, I=6+4 이다.

 

사실 이 식을 잘 보면,
cur(E) = prev(E) + prev(I)
cur(I) = (prev(E) * 2) + prev(I)
로 나타낼 수 있다.

코드

const sol = (n) => {
  const MOD = 9901;
  const dp = Array.from({ length: 2 }, () => new Array(2).fill(0));
  dp[1][0] = 1;
  dp[1][1] = 2;
  for (let i = 2; i <= n; i++) {
    const cur = i % 2;
    let prev;
    if (cur === 1) prev = 0;
    else prev = 1;
    dp[cur][0] = (dp[prev][0] + dp[prev][1]) % MOD;
    dp[cur][1] = (dp[prev][0] * 2 + dp[prev][1]) % MOD;
  }
  console.log((dp[n % 2][0] + dp[n % 2][1]) % MOD);
};

require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    sol(+line);
  })
  .on("close", () => {
    process.exit();
  });

 

dp 배열 크기를 N x 2로 선언해도 되지만,

다음과 같이 2 x 2 크기로 선언하고 

홀짝에 따라 0,1번 인덱스로 이동하면서 연산을 수행할 수 있다.

저작자표시 (새창열림)

'DS & Algorithm > baekjoon' 카테고리의 다른 글

[백준] 13023번 ABCDE - JavaScript(NodeJS)  (0) 2021.05.27
[백준] 1932번 정수삼각형 - JavaScript(NodeJS)  (0) 2021.05.17
[백준] 1406번 에디터 - JavaScript(NodeJS)  (2) 2021.05.02
[백준] 9093번 단어 뒤집기 - JavaScript(NodeJS)  (0) 2021.05.01
[백준] 10828번 스택 - JavaScript(NodeJS)  (0) 2021.05.01
  • 문제
  •  
  • 풀이
  • 코드
'DS & Algorithm/baekjoon' 카테고리의 다른 글
  • [백준] 13023번 ABCDE - JavaScript(NodeJS)
  • [백준] 1932번 정수삼각형 - JavaScript(NodeJS)
  • [백준] 1406번 에디터 - JavaScript(NodeJS)
  • [백준] 9093번 단어 뒤집기 - JavaScript(NodeJS)
jiho_bae
jiho_bae
하루에 한 걸음씩

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.