내일배움 과제/코딩테스트
알고리즘 82번 멀리뛰기
GREEN나무
2025. 2. 24. 07:51
728x90
URL : https://school.programmers.co.kr/learn/courses/30/lessons/12914
JS
문제
더보기
문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.
제한 사항
n은 1 이상, 2000 이하인 정수입니다.
입출력 예
| n | result |
| 4 | 5 |
| 3 | 3 |
입출력 예 설명
입출력 예 #1
위에서 설명한 내용과 같습니다.
입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.
계획
1,2칸씩 건너간 경위의 수 구하기
1234567로 나눈 나머지 반환
참고, 풀이
효진이는 한 번에 1칸 또는 2칸을 뛸 수 있다.
즉, n 번째 칸에 도달하는 방법은 바로 전 칸(n-1)에서 한 칸 뛰거나,
혹은 두 칸 전(n-2)에서 두 칸 뛰는 방법 두 가지뿐임.
즉, n에 도달하는 방법의 개수는 (n-1)번째 경우의 수 + (n-2)번째 경우의 수와 같다.
이를 식으로 나타내면: f(n)=f(n−1)+f(n−2)
즉 문제는 피보나치 수열과 동일한 패턴을 따른다.
답
const solution = (n) => {
const MOD = 1234567;
let dp = [0, 1, 2]; // dp[1] = 1, dp[2] = 2
for (let i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
}
return dp[n];
};코드 간략화하기
function solution(n) {
let a = 1, b = 2;
for (let i = 3; i <= n; i++) {
[a, b] = [b, (a + b) % 1234567];
}
return n === 1 ? a : b;
}다른사람 답
피보나치 수열을 1234567로 나눈 나머지값을 가지 배열을 적고 n번째 값을 반환
더보기
/*
* 1 칸을 뛰는 방법 = 1 가지
* 2 칸을 뛰는 방법 = 2 가지
* (n+2 칸을 뛰는 방법) = (n+1 칸을 뛰는 방법) + (n 칸을 뛰는 방법)
* f_1 = 1, f_2 = 2 인 피보나치 수열
*
*/
function solution(n) {
return [
0,
1,
2,
3,
5,
8,
13,
21,
34,
55,
89,
144,
233,
377,
610,
987,
1597,
2584,
4181,
6765,
10946,
17711,
28657,
46368,
75025,
121393,
196418,
317811,
514229,
832040,
111702,
943742,
1055444,
764619,
585496,
115548,
701044,
816592,
283069,
1099661,
148163,
13257,
161420,
174677,
336097,
510774,
846871,
123078,
969949,
1093027,
828409,
686869,
280711,
967580,
13724,
981304,
995028,
741765,
502226,
9424,
511650,
521074,
1032724,
319231,
117388,
436619,
554007,
990626,
310066,
66125,
376191,
442316,
818507,
26256,
844763,
871019,
481215,
117667,
598882,
716549,
80864,
797413,
878277,
441123,
84833,
525956,
610789,
1136745,
512967,
415145,
928112,
108690,
1036802,
1145492,
947727,
858652,
571812,
195897,
767709,
963606,
496748,
225787,
722535,
948322,
436290,
150045,
586335,
736380,
88148,
824528,
912676,
502637,
180746,
683383,
864129,
312945,
1177074,
255452,
197959,
453411,
651370,
1104781,
521584,
391798,
913382,
70613,
983995,
1054608,
804036,
624077,
193546,
817623,
1011169,
594225,
370827,
965052,
101312,
1066364,
1167676,
999473,
932582,
697488,
395503,
1092991,
253927,
112351,
366278,
478629,
844907,
88969,
933876,
1022845,
722154,
510432,
1232586,
508451,
506470,
1014921,
286824,
67178,
354002,
421180,
775182,
1196362,
736977,
698772,
201182,
899954,
1101136,
766523,
633092,
165048,
798140,
963188,
526761,
255382,
782143,
1037525,
585101,
388059,
973160,
126652,
1099812,
1226464,
1091709,
1083606,
940748,
789787,
495968,
51188,
547156,
598344,
1145500,
509277,
420210,
929487,
115130,
1044617,
1159747,
969797,
894977,
630207,
290617,
920824,
1211441,
897698,
874572,
537703,
177708,
715411,
893119,
373963,
32515,
406478,
438993,
845471,
49897,
895368,
945265,
606066,
316764,
922830,
5027,
927857,
932884,
626174,
324491,
950665,
40589,
991254,
1031843,
788530,
585806,
139769,
725575,
865344,
356352,
1221696,
343481,
330610,
674091,
1004701,
444225,
214359,
658584,
872943,
296960,
1169903,
232296,
167632,
399928,
567560,
967488,
300481,
33402,
333883,
367285,
701168,
1068453,
535054,
368940,
903994,
38367,
942361,
980728,
688522,
434683,
1123205,
323321,
211959,
535280,
747239,
47952,
795191,
843143,
403767,
12343,
416110,
428453,
844563,
38449,
883012,
921461,
569906,
256800,
826706,
1083506,
675645,
524584,
1200229,
490246,
455908,
946154,
167495,
1113649,
46577,
1160226,
1206803,
1132462,
1104698,
1002593,
872724,
640750,
278907,
919657,
1198564,
883654,
847651,
496738,
109822,
606560,
716382,
88375,
804757,
893132,
463322,
121887,
585209,
707096,
57738,
764834,
822572,
352839,
1175411,
293683,
234527,
528210,
762737,
56380,
819117,
875497,
460047,
100977,
561024,
662001,
1223025,
650459,
638917,
54809,
693726,
748535,
207694,
956229,
1163923,
885585,
814941,
465959,
46333,
512292,
558625,
1070917,
394975,
231325,
626300,
857625,
249358,
1106983,
121774,
1228757,
115964,
110154,
226118,
336272,
562390,
898662,
226485,
1125147,
117065,
7645,
124710,
132355,
257065,
389420,
646485,
1035905,
447823,
249161,
696984,
946145,
408562,
120140,
528702,
648842,
1177544,
591819,
534796,
1126615,
426844,
318892,
745736,
1064628,
575797,
405858,
981655,
152946,
1134601,
52980,
1187581,
5994,
1193575,
1199569,
1158577,
1123579,
1047589,
936601,
749623,
451657,
1201280,
418370,
385083,
803453,
1188536,
757422,
711391,
234246,
945637,
1179883,
890953,
836269,
492655,
94357,
587012,
681369,
33814,
715183,
748997,
229613,
978610,
1208223,
952266,
925922,
643621,
334976,
978597,
79006,
1057603,
1136609,
959645,
861687,
586765,
213885,
800650,
1014535,
580618,
360586,
941204,
67223,
1008427,
1075650,
849510,
690593,
305536,
996129,
67098,
1063227,
1130325,
958985,
854743,
579161,
199337,
778498,
977835,
521766,
265034,
786800,
1051834,
604067,
421334,
1025401,
212168,
3002,
215170,
218172,
433342,
651514,
1084856,
501803,
352092,
853895,
1205987,
825315,
796735,
387483,
1184218,
337134,
286785,
623919,
910704,
300056,
1210760,
276249,
252442,
528691,
781133,
75257,
856390,
931647,
553470,
250550,
804020,
1054570,
624023,
444026,
1068049,
277508,
110990,
388498,
499488,
887986,
152907,
1040893,
1193800,
1000126,
959359,
724918,
449710,
1174628,
389771,
329832,
719603,
1049435,
534471,
349339,
883810,
1233149,
882392,
880974,
528799,
175206,
704005,
879211,
348649,
1227860,
341942,
335235,
677177,
1012412,
455022,
232867,
687889,
920756,
374078,
60267,
434345,
494612,
928957,
189002,
1117959,
72394,
1190353,
28180,
1218533,
12146,
1230679,
8258,
4370,
12628,
16998,
29626,
46624,
76250,
122874,
199124,
321998,
521122,
843120,
129675,
972795,
1102470,
840698,
708601,
314732,
1023333,
103498,
1126831,
1230329,
1122593,
1118355,
1006381,
890169,
661983,
317585,
979568,
62586,
1042154,
1104740,
912327,
782500,
460260,
8193,
468453,
476646,
945099,
187178,
1132277,
84888,
1217165,
67486,
50084,
117570,
167654,
285224,
452878,
738102,
1190980,
694515,
650928,
110876,
761804,
872680,
399917,
38030,
437947,
475977,
913924,
155334,
1069258,
1224592,
1059283,
1049308,
874024,
688765,
328222,
1016987,
110642,
1127629,
3704,
1131333,
1135037,
1031803,
932273,
729509,
427215,
1156724,
349372,
271529,
620901,
892430,
278764,
1171194,
215391,
152018,
367409,
519427,
886836,
171696,
1058532,
1230228,
1054193,
1049854,
869480,
684767,
319680,
1004447,
89560,
1094007,
1183567,
1043007,
992007,
800447,
557887,
123767,
681654,
805421,
252508,
1057929,
75870,
1133799,
1209669,
1108901,
1084003,
958337,
807773,
531543,
104749,
636292,
741041,
142766,
883807,
1026573,
675813,
467819,
1143632,
376884,
285949,
662833,
948782,
377048,
91263,
468311,
559574,
1027885,
352892,
146210,
499102,
645312,
1144414,
555159,
465006,
1020165,
250604,
36202,
286806,
323008,
609814,
932822,
308069,
6324,
314393,
320717,
635110,
955827,
356370,
77630,
434000,
511630,
945630,
222693,
1168323,
156449,
90205,
246654,
336859,
583513,
920372,
269318,
1189690,
224441,
179564,
404005,
583569,
987574,
336576,
89583,
426159,
515742,
941901,
223076,
1164977,
153486,
83896,
237382,
321278,
558660,
879938,
204031,
1083969,
53433,
1137402,
1190835,
1093670,
1049938,
909041,
724412,
398886,
1123298,
287617,
176348,
463965,
640313,
1104278,
510024,
379735,
889759,
34927,
924686,
959613,
649732,
374778,
1024510,
164721,
1189231,
119385,
74049,
193434,
267483,
460917,
728400,
1189317,
683150,
637900,
86483,
724383,
810866,
300682,
1111548,
177663,
54644,
232307,
286951,
519258,
806209,
90900,
897109,
988009,
650551,
403993,
1054544,
223970,
43947,
267917,
311864,
579781,
891645,
236859,
1128504,
130796,
24733,
155529,
180262,
335791,
516053,
851844,
133330,
985174,
1118504,
869111,
753048,
387592,
1140640,
293665,
199738,
493403,
693141,
1186544,
645118,
597095,
7646,
604741,
612387,
1217128,
594948,
577509,
1172457,
515399,
453289,
968688,
187410,
1156098,
108941,
30472,
139413,
169885,
309298,
479183,
788481,
33097,
821578,
854675,
441686,
61794,
503480,
565274,
1068754,
399461,
233648,
633109,
866757,
265299,
1132056,
162788,
60277,
223065,
283342,
506407,
789749,
61589,
851338,
912927,
529698,
208058,
737756,
945814,
449003,
160250,
609253,
769503,
144189,
913692,
1057881,
737006,
560320,
62759,
623079,
685838,
74350,
760188,
834538,
360159,
1194697,
320289,
280419,
600708,
881127,
247268,
1128395,
141096,
34924,
176020,
210944,
386964,
597908,
984872,
348213,
98518,
446731,
545249,
991980,
302662,
60075,
362737,
422812,
785549,
1208361,
759343,
733137,
257913,
991050,
14396,
1005446,
1019842,
790721,
575996,
132150,
708146,
840296,
313875,
1154171,
233479,
153083,
386562,
539645,
926207,
231285,
1157492,
154210,
77135,
231345,
308480,
539825,
848305,
153563,
1001868,
1155431,
922732,
843596,
531761,
140790,
672551,
813341,
251325,
1064666,
81424,
1146090,
1227514,
1139037,
1131984,
1036454,
933871,
735758,
435062,
1170820,
371315,
307568,
678883,
986451,
430767,
182651,
613418,
796069,
174920,
970989,
1145909,
882331,
793673,
441437,
543,
441980,
442523,
884503,
92459,
976962,
1069421,
811816,
646670,
223919,
870589,
1094508,
730530,
590471,
86434,
676905,
763339,
205677,
969016,
1174693,
909142,
849268,
523843,
138544,
662387,
800931,
228751,
1029682,
23866,
1053548,
1077414,
896395,
739242,
401070,
1140312,
306815,
212560,
519375,
731935,
16743,
748678,
765421,
279532,
1044953,
89918,
1134871,
1224789,
1125093,
1115315,
1005841,
886589,
657863,
309885,
967748,
43066,
1010814,
1053880,
830127,
649440,
245000,
894440,
1139440,
799313,
704186,
268932,
973118,
7483,
980601,
988084,
734118,
487635,
1221753,
474821,
462007,
936828,
164268,
1101096,
30797,
1131893,
1162690,
1060016,
988139,
813588,
567160,
146181,
713341,
859522,
338296,
1197818,
301547,
264798,
566345,
831143,
162921,
994064,
1156985,
916482,
838900,
520815,
125148,
645963,
771111,
182507,
953618,
1136125,
855176,
756734,
377343,
1134077,
276853,
176363,
453216,
629579,
1082795,
477807,
326035,
803842,
1129877,
699152,
594462,
59047,
653509,
712556,
131498,
844054,
975552,
585039,
326024,
911063,
2520,
913583,
916103,
595119,
276655,
871774,
1148429,
785636,
699498,
250567,
950065,
1200632,
916130,
882195,
563758,
211386,
775144,
986530,
527107,
279070,
806177,
1085247,
656857,
507537,
1164394,
437364,
367191,
804555,
1171746,
741734,
678913,
186080,
864993,
1051073,
681499,
498005,
1179504,
442942,
387879,
830821,
1218700,
814954,
799087,
379474,
1178561,
323468,
267462,
590930,
858392,
214755,
1073147,
53335,
1126482,
1179817,
1071732,
1016982,
854147,
636562,
256142,
892704,
1148846,
806983,
721262,
293678,
1014940,
74051,
1088991,
1163042,
1017466,
945941,
728840,
440214,
1169054,
374701,
309188,
683889,
993077,
442399,
200909,
643308,
844217,
252958,
1097175,
115566,
1212741,
93740,
71914,
165654,
237568,
403222,
640790,
1044012,
450235,
259680,
709915,
969595,
444943,
179971,
624914,
804885,
195232,
1000117,
1195349,
960899,
921681,
648013,
335127,
983140,
83700,
1066840,
1150540,
982813,
898786,
647032,
311251,
958283,
34967,
993250,
1028217,
786900,
580550,
132883,
713433,
846316,
325182,
1171498,
262113,
199044,
461157,
660201,
1121358,
546992,
433783,
980775,
179991,
1160766,
106190,
32389,
138579,
170968,
309547,
480515,
790062,
36010,
826072,
862082,
453587,
81102,
534689,
615791,
1150480,
531704,
447617,
979321,
192371,
1171692,
129496,
66621,
196117,
262738,
458855,
721593,
1180448,
667474,
613355,
46262,
659617,
705879,
130929,
836808,
967737,
569978,
303148,
873126,
1176274,
814833,
756540,
336806,
1093346,
195585,
54364,
249949,
304313,
554262,
858575,
178270,
1036845,
1215115,
1017393,
997941,
780767,
544141,
90341,
634482,
724823,
124738,
849561,
974299,
589293,
329025,
918318,
12776,
931094,
943870,
640397,
349700,
990097,
105230,
1095327,
1200557,
1061317,
1027307,
854057,
646797,
266287,
913084,
1179371,
857888,
802692,
426013,
1228705,
420151,
414289,
834440,
14162,
848602,
862764,
476799,
104996,
581795,
686791,
34019,
720810,
754829,
241072,
995901,
2406,
998307,
1000713,
764453,
530599,
60485,
591084,
651569,
8086,
659655,
667741,
92829,
760570,
853399,
379402,
1232801,
377636,
375870,
753506,
1129376,
648315,
543124,
1191439,
499996,
456868,
956864,
179165,
1136029,
80627,
1216656,
62716,
44805,
107521,
152326,
259847,
412173,
672020,
1084193,
521646,
371272,
892918,
29623,
922541,
952164,
640138,
357735,
997873,
121041,
1118914,
5388,
1124302,
1129690,
1019425,
914548,
699406,
379387,
1078793,
223613,
67839,
291452,
359291,
650743,
1010034,
426210,
201677,
627887,
829564,
222884,
1052448,
40765,
1093213,
1133978,
992624,
892035,
650092,
307560,
957652,
30645,
988297,
1018942,
772672,
557047,
95152,
652199,
747351,
164983,
912334,
1077317,
755084,
597834,
118351,
716185,
834536,
316154,
1150690,
232277,
148400,
380677,
529077,
909754,
204264,
1114018,
83715,
1197733,
46881,
10047,
56928,
66975,
123903,
190878,
314781,
505659,
820440,
91532,
911972,
1003504,
680909,
449846,
1130755,
346034,
242222,
588256,
830478,
184167,
1014645,
1198812,
978890,
943135,
687458,
396026,
1083484,
244943,
93860,
338803,
432663,
771466,
1204129,
741028,
710590,
217051,
927641,
1144692,
837766,
747891,
351090,
1098981,
215504,
79918,
295422,
375340,
670762,
1046102,
482297,
293832,
776129,
1069961,
611523,
446917,
1058440,
270790,
94663,
365453,
460116,
825569,
51118,
876687,
927805,
569925,
263163,
833088,
1096251,
694772,
556456,
16661,
573117,
589778,
1162895,
518106,
446434,
964540,
176407,
1140947,
82787,
1223734,
71954,
61121,
133075,
194196,
327271,
521467,
848738,
135638,
984376,
1120014,
869823,
755270,
390526,
1145796,
301755,
212984,
514739,
727723,
7895,
735618,
743513,
244564,
988077,
1232641,
986151,
984225,
735809,
485467,
1221276,
472176,
458885,
931061,
155379,
1086440,
7252,
1093692,
1100944,
960069,
826446,
551948,
143827,
695775,
839602,
300810,
1140412,
206655,
112500,
319155,
431655,
750810,
1182465,
698708,
646606,
110747,
757353,
868100,
390886,
24419,
415305,
439724,
855029,
60186,
915215,
975401,
656049,
396883,
1052932,
215248,
33613,
248861,
282474,
531335,
813809,
110577,
924386,
1034963,
724782,
525178,
15393,
540571,
555964,
1096535,
417932,
279900,
697832,
977732,
440997,
184162,
625159,
809321,
199913,
1009234,
1209147,
983814,
958394,
707641,
431468,
1139109,
336010,
240552,
576562,
817114,
159109,
976223,
1135332,
876988,
777753,
420174,
1197927,
383534,
346894,
730428,
1077322,
573183,
415938,
989121,
170492,
1159613,
95538,
20584,
116122,
136706,
252828,
389534,
642362,
1031896,
439691,
237020,
676711,
913731,
355875,
35039,
390914,
425953,
816867,
8253,
825120,
833373,
423926,
22732,
446658,
469390,
916048,
150871,
1066919,
1217790,
1050142,
1033365,
848940,
647738,
262111,
909849,
1171960,
847242,
784635,
397310,
1181945,
344688,
292066,
636754,
928820,
331007,
25260,
356267,
381527,
737794,
1119321,
622548,
507302,
1129850,
402585,
297868,
700453,
998321,
464207,
227961,
692168,
920129,
377730,
63292,
441022,
504314,
945336,
215083,
1160419,
140935,
66787,
207722,
274509,
482231,
756740,
4404,
761144,
765548,
292125,
1057673,
115231,
1172904,
53568,
1226472,
45473,
37378,
82851,
120229,
203080,
323309,
526389,
849698,
141520,
991218,
1132738,
889389,
787560,
442382,
1229942,
437757,
433132,
870889,
69454,
940343,
1009797,
715573,
490803,
1206376,
462612,
434421,
897033,
96887,
993920,
1090807,
850160,
706400,
321993,
1028393,
115819,
1144212,
25464,
1169676,
1195140,
1130249,
1090822,
986504,
842759,
594696,
202888,
797584,
1000472,
563489,
329394,
892883,
1222277,
880593,
868303,
514329,
148065,
662394,
810459,
238286,
1048745,
52464,
1101209,
1153673,
1020315,
939421,
725169,
430023,
1155192,
350648,
271273,
621921,
893194,
280548,
1173742,
219723,
158898,
378621,
537519,
916140,
219092,
1135232,
119757,
20422,
140179,
160601,
300780,
461381,
762161,
1223542,
751136,
740111,
256680,
996791,
18904,
1015695,
1034599,
815727,
615759,
196919,
812678,
1009597,
587708,
362738,
950446,
78617,
1029063,
1107680,
902176,
775289,
442898,
1218187,
426518,
410138,
836656,
12227,
848883,
861110,
475426,
101969,
577395,
679364,
22192,
701556,
723748,
190737,
914485,
1105222,
785140,
655795,
206368,
862163,
1068531,
696127,
530091,
1226218,
521742,
513393,
1035135,
313961,
114529,
428490,
543019,
971509,
279961,
16903,
296864,
313767,
610631,
924398,
300462,
1224860,
290755,
281048,
571803,
852851,
190087,
1042938,
1233025,
1041396,
1039854,
846683,
651970,
264086,
916056,
1180142,
861631,
807206,
434270,
6909,
441179,
448088,
889267,
102788,
992055,
1094843,
852331,
712607,
330371,
1042978,
138782,
1181760,
85975,
33168,
119143,
152311,
271454,
423765,
695219,
1118984,
579636,
464053,
1043689,
273175,
82297,
355472,
437769,
793241,
1231010,
789684,
786127,
341244,
1127371,
234048,
126852,
360900,
487752,
848652,
101837,
950489,
1052326,
768248,
586007,
119688,
705695,
825383,
296511,
1121894,
183838,
71165,
255003,
326168,
581171,
907339,
253943,
1161282,
180658,
107373,
288031,
395404,
683435,
1078839,
527707,
371979,
899686,
37098,
936784,
973882,
676099,
415414,
1091513,
272360,
129306,
401666,
530972,
932638,
229043,
1161681,
156157,
83271,
239428,
322699,
562127,
884826,
212386,
1097212,
75031,
1172243,
12707,
1184950,
1197657,
1148040,
1111130,
1024603,
901166,
691202,
357801,
1049003,
172237,
1221240,
158910,
145583,
304493,
450076,
754569,
1204645,
724647
][n];
}