おつりを出す
4449 ワード
https://programmers.co.kr/learn/courses/30/lessons/12907
問題の説明
Finnはコンビニで夜間アルバイトをしています.夜、お客さんが多すぎて退屈していたFinnがお客さんに小銭を探してあげたとき、方法を探すことにしました.
例えば、お客様に5元を探して、1元、2元、5元を持っている場合は、以下の4つの方法で5元を探すことができます.
5元で金を探す.
1元は3個、2元は1個で探します.
1元で1個、2元で取り戻します.
5元で1つ探します.
取り戻した金額nとFinnが現在持っているお金の種類moneyをパラメータとする必要がある場合は、Finnがn元の取り戻し方法の数を返すように解く関数を完了してください.
せいげんじょうけん
nは100000以下の自然数である.
通貨単位は100種類以下です.
すべての通貨が無限であると仮定します.
答えは大きくなるかもしれませんが、10万07の残りを返してください.
I/O例
nmoneyresult5[1,2,5]4
問題を解く
小銭からn元までのすべての偽整数を求める方法.
0元になる方法は1つしかないので、Change配列の0番目のインデックスに1を入れます.
コインの数だけ繰り返し回します.
探していたお金を1元からn元まで返してください.
つり方
たとえば
nは5であり、小銭がある場合[1,2,5]元、例1
jが1の場合、mony[i]は1であるため、等しいかまたは小さいので、おつりchange[1]は0でchange[1-1(mony[i])を100000007で割った後に余剰値を加算しなければならない.
change[1]=0+change[0]%1億7,change[0]は1であるためchange[1]は1である.
jが2であってもchange[2]は2である.
1を作成できる場合は1種類あります
2を作成できる場合は1+1種類あります
.
.
.
5を作成できる場合は、1+1+1+1+1を使用することもできます.
change = [1,1,1,1,1,1]
iが0の場合、changeの値はこうなります.
iが1ならコインの値段は2元です
2元の結果.
結果はchange=[1,2,3,3].
5元なら5元のコインを探せばいいです.
change=[1,2,2,3,4]の小銭の配分方法が現れた.
1+1+1+1+1
1+1+1+2
1+2+2
5
答えは4です.
金をさがす
問題の説明
Finnはコンビニで夜間アルバイトをしています.夜、お客さんが多すぎて退屈していたFinnがお客さんに小銭を探してあげたとき、方法を探すことにしました.
例えば、お客様に5元を探して、1元、2元、5元を持っている場合は、以下の4つの方法で5元を探すことができます.
5元で金を探す.
1元は3個、2元は1個で探します.
1元で1個、2元で取り戻します.
5元で1つ探します.
取り戻した金額nとFinnが現在持っているお金の種類moneyをパラメータとする必要がある場合は、Finnがn元の取り戻し方法の数を返すように解く関数を完了してください.
せいげんじょうけん
nは100000以下の自然数である.
通貨単位は100種類以下です.
すべての通貨が無限であると仮定します.
答えは大きくなるかもしれませんが、10万07の残りを返してください.
I/O例
nmoneyresult5[1,2,5]4
問題を解く
function solution(n, money) {
let change = [1];
for(let i = 1; i <= n; i++)
change[i] = 0;
for(let i = 0; i < money.length; i++) {
for(let j = 1; j <= n; j++)
if(money[i] <= j)
change[j] += change[j-money[i]]%1000000007;
}
return change[n];
}
先日、キャンプをスタートさせて一度問題を解決したことがある.小銭からn元までのすべての偽整数を求める方法.
0元になる方法は1つしかないので、Change配列の0番目のインデックスに1を入れます.
コインの数だけ繰り返し回します.
探していたお金を1元からn元まで返してください.
つり方
たとえば
nは5であり、小銭がある場合[1,2,5]元、例1
jが1の場合、mony[i]は1であるため、等しいかまたは小さいので、おつりchange[1]は0でchange[1-1(mony[i])を100000007で割った後に余剰値を加算しなければならない.
change[1]=0+change[0]%1億7,change[0]は1であるためchange[1]は1である.
jが2であってもchange[2]は2である.
1を作成できる場合は1種類あります
2を作成できる場合は1+1種類あります
.
.
.
5を作成できる場合は、1+1+1+1+1を使用することもできます.
change = [1,1,1,1,1,1]
iが0の場合、changeの値はこうなります.
iが1ならコインの値段は2元です
2元の結果.
結果はchange=[1,2,3,3].
5元なら5元のコインを探せばいいです.
change=[1,2,2,3,4]の小銭の配分方法が現れた.
1+1+1+1+1
1+1+1+2
1+2+2
5
答えは4です.
Reference
この問題について(おつりを出す), 我々は、より多くの情報をここで見つけました https://velog.io/@source39/알고리즘-문제-풀이-거스름-돈テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol