白駿1309動物園-Nodejs
このポスターは白準1309号動物園のプールを描いている.質問リンク
コードはjavascriptで書かれています.
動物園には横2間、横N間の下のようなケージがあります.
ライオンをケージに閉じ込めるときは、横にも縦にも置けません. 2 xNアレイにライオンを配置する場合は、どのくらいのライオンがいるかを決定するプログラムを作成してください. ライオンを1匹置かない場合も、1つの場合の数字で計算します.
第1行は我々のサイズN(1≦N≦100000)を与える.
1行目にライオンが置かれている場合は、残りの数字9901を出力します.
この問題は
例を挙げて詳しく説明します.Nが3であると仮定する
N-1行目、すなわち1行目 1行は空です.これは、0行目について可能であれば個数を求めることができることを意味します. Nが0の場合の数字は1です. 上の行は空なので、N行目については、可能な場合は「空」、「左ライオン」、「右ライオン」の3種類があります. したがって、N−1動作が空の場合、可能な数は
N-1行目、すなわち1行目 1行は空ではありません.すなわち、「N-1の数字-上の行が空の数字」を考慮します. N-1の数=D[2]=3 上記の動作が空の場合、数字=D[1]=1 上記の行為が空であるため、N行目については、可能な場合はそれぞれ2種類ある.(空白または対角線方向) したがって、N−1行が空でない場合、可能な数は
従って、Nが3の場合、総数は
N-1行目、すなわち2行目 2行が空であることは、最初の行について可能であれば、1つの数字を求めることができることを意味する. Nが1の場合の数字は3です. 上の行は空なので、N行目については、可能な場合は「空」、「左ライオン」、「右ライオン」の3種類があります. したがって、N−1動作が空の場合、可能な数字は3*3=9である.
N-1行目、すなわち2行目 1行は空ではありません.すなわち、「N-1の数字-上の行が空の数字」を考慮します. N-1の数=D[2]=7 上記の動作が空の場合、数字=D[1]=3 上記の行為が空であるため、N行目については、可能な場合はそれぞれ2種類ある.(空白または対角線方向) したがって、N-1行が空でない場合、可能な数は(7-3)*2=8種類である.
したがって,Nが4の場合,総数は
上記の例では、ルールを見つけることができます.
てんかしき
D[N] = D[N-2] + D[N-1] * 2
コードはjavascriptで書かれています.
質問する
1.問題の説明
動物園には横2間、横N間の下のようなケージがあります.
2.入力
第1行は我々のサイズN(1≦N≦100000)を与える.
3.出力
1行目にライオンが置かれている場合は、残りの数字9901を出力します.
に答える
この問題は
i번째 행
の配置状態に依存するため、DPによって解決することができる.ろんり
例を挙げて詳しく説明します.Nが3であると仮定する
i-1번째 행
問題にライオンが1匹も配置されていない場合、1つの場合の数字と仮定すると1になります.[N = 0]
「空」「左ライオン」「右ライオン」の3つのケースがあります.[N = 1]
には7つのケースがありますN-1行目、すなわち1行目
[N = 3]
できれば、数量=3비어있을 때
である.N-1行目、すなわち1行目
1*3 = 3가지
できれば数量=4비어있지 않을 때
である.従って、Nが3の場合、総数は
(3-1)*2 = 4가지
種である.3+4 = 7
17の場合N-1行目、すなわち2行目
[N = 4]
できれば数量=9N-1行目、すなわち2行目
비어있을 때
できれば数量=8したがって,Nが4の場合,総数は
비어있지 않을 때
種である.てんかしき
上記の例では、ルールを見つけることができます.
てんかしき
D[N] = D[N-2] + D[N-1] * 2
完全なコード
const input = require('fs').readFileSync('/dev/stdin').toString();
const N = Number(input);
const dp = [1, 3].concat(new Array(N - 1).fill(0));
for (let i = 2; i <= N; i++) {
dp[i] = (dp[i-2] + dp[i-1]*2) % 9901;
}
console.log(dp[N]);
Reference
この問題について(白駿1309動物園-Nodejs), 我々は、より多くの情報をここで見つけました https://velog.io/@dev-redo/백준-1309-동물원-node.jsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol