Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
16 lines (15 sloc) 48.2 KB
---
layout : article
title: "[백준] 11051번 C/C++ 풀이 _ 이항 계수 2"
aside:
toc: true
tags: Algorithm
category : Algorithm
author: melonicedlatte
published : True
hellogohn_num : 360
key : 2018-09-26-025516
---
<h3>출처 :&nbsp;<a href="https://www.acmicpc.net/problem/11051">https://www.acmicpc.net/problem/11051</a>&nbsp;</h3><div class="col-md-12" style="width: 970px; color: rgb(51, 51, 51); font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-size: 13px; border-radius: 0px !important;"><div class="page-header" style="border-radius: 0px !important;"><h1 style="margin-top: 5px; font-size: 28px; font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-weight: normal; line-height: 35px; color: rgb(88, 95, 105); text-shadow: none; border-radius: 0px !important;"><span id="problem_title" class="" style="border-radius: 0px !important;">이항 계수 2</span><div class="btn-group pull-right problem-button" style="border-radius: 0px !important;"><button class="btn btn-default" type="button" id="favorite_button" data-favorite="0" style="border-radius: 4px; font-weight: 400; line-height: 1.42857; font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; text-transform: none; padding: 6px 12px; box-shadow: none; outline: 0px !important;"><span class="glyphicon glyphicon-star-empty" id="favorite_image" style="border-radius: 0px !important;"></span></button></div></h1></div></div><div class="col-md-12" style="width: 970px; color: rgb(51, 51, 51); font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-size: 13px; border-radius: 0px !important;"><div class="table-responsive" style="border-radius: 0px !important;"><table class="table" id="problem-info" style="width: 940px; border-radius: 0px !important;"><thead style="border-radius: 0px !important;"><tr style="border-radius: 0px !important;"><th style="line-height: 1.42857; border-bottom: none; width: 151px; border-radius: 0px !important;">시간 제한</th><th style="line-height: 1.42857; border-bottom: none; width: 151px; border-radius: 0px !important;">메모리 제한</th><th style="line-height: 1.42857; border-bottom: none; width: 160px; border-radius: 0px !important;">제출</th><th style="line-height: 1.42857; border-bottom: none; width: 160px; border-radius: 0px !important;">정답</th><th style="line-height: 1.42857; border-bottom: none; width: 159px; border-radius: 0px !important;">맞은 사람</th><th style="line-height: 1.42857; border-bottom: none; width: 159px; border-radius: 0px !important;">정답 비율</th></tr></thead><tbody style="border-radius: 0px !important;"><tr style="border-radius: 0px !important;"><td style="line-height: 1.42857; border-radius: 0px !important;">1 초</td><td style="line-height: 1.42857; border-radius: 0px !important;">256 MB</td><td style="line-height: 1.42857; border-radius: 0px !important;">10518</td><td style="line-height: 1.42857; border-radius: 0px !important;">3911</td><td style="line-height: 1.42857; border-radius: 0px !important;">3111</td><td style="line-height: 1.42857; border-radius: 0px !important;">38.379%</td></tr></tbody></table></div></div><div id="problem-body" style="color: rgb(51, 51, 51); font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-size: 13px; border-radius: 0px !important;"><div class="col-md-12" style="width: 970px; border-radius: 0px !important;"><section id="description" style="border-radius: 0px !important;"><div class="headline" style="margin: 10px 0px 25px; border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px !important;"><h2 style="font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-weight: normal; line-height: 33px; color: rgb(88, 95, 105); margin: 0px 0px -2px; font-size: 22px; text-shadow: none; padding-bottom: 5px; display: inline-block; border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px !important;">문제</h2></div><div id="problem_description" style="font-size: medium; line-height: 30px; border-radius: 0px !important;"><p style="margin-top: 0px; margin-bottom: 10px; color: rgb(85, 85, 85); border-radius: 0px !important;">자연수&nbsp;<span class="MathJax_Preview" style="color: inherit; border-radius: 0px !important;"></span><span class="MathJax_SVG" id="MathJax-Element-1-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>N</mi></math>" role="presentation" style="display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; border-radius: 0px !important;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="2.064ex" height="1.994ex" viewBox="0 -755.9 888.5 858.4" role="img" focusable="false" style="vertical-align: -0.238ex;" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#MJMATHI-4E" x="0" y="0"><path stroke-width="1" id="MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></use></g></svg><span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; transition: none 0s ease 0s; border-radius: 0px !important; position: absolute !important; padding: 1px 0px 0px !important; border: 0px !important; height: 1px !important; width: 1px !important; overflow: hidden !important; display: block !important;"><math xmlns="http://www.w3.org/1998/Math/MathML">N</math></span></span>과 정수&nbsp;<span class="MathJax_Preview" style="color: inherit; border-radius: 0px !important;"></span><span class="MathJax_SVG" id="MathJax-Element-2-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>K</mi></math>" role="presentation" style="display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; border-radius: 0px !important;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="2.066ex" height="1.994ex" viewBox="0 -755.9 889.5 858.4" role="img" focusable="false" style="vertical-align: -0.238ex;" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#MJMATHI-4B" x="0" y="0"><path stroke-width="1" id="MJMATHI-4B" d="M285 628Q285 635 228 637Q205 637 198 638T191 647Q191 649 193 661Q199 681 203 682Q205 683 214 683H219Q260 681 355 681Q389 681 418 681T463 682T483 682Q500 682 500 674Q500 669 497 660Q496 658 496 654T495 648T493 644T490 641T486 639T479 638T470 637T456 637Q416 636 405 634T387 623L306 305Q307 305 490 449T678 597Q692 611 692 620Q692 635 667 637Q651 637 651 648Q651 650 654 662T659 677Q662 682 676 682Q680 682 711 681T791 680Q814 680 839 681T869 682Q889 682 889 672Q889 650 881 642Q878 637 862 637Q787 632 726 586Q710 576 656 534T556 455L509 418L518 396Q527 374 546 329T581 244Q656 67 661 61Q663 59 666 57Q680 47 717 46H738Q744 38 744 37T741 19Q737 6 731 0H720Q680 3 625 3Q503 3 488 0H478Q472 6 472 9T474 27Q478 40 480 43T491 46H494Q544 46 544 71Q544 75 517 141T485 216L427 354L359 301L291 248L268 155Q245 63 245 58Q245 51 253 49T303 46H334Q340 37 340 35Q340 19 333 5Q328 0 317 0Q314 0 280 1T180 2Q118 2 85 2T49 1Q31 1 31 11Q31 13 34 25Q38 41 42 43T65 46Q92 46 125 49Q139 52 144 61Q147 65 216 339T285 628Z"></path></use></g></svg><span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; transition: none 0s ease 0s; border-radius: 0px !important; position: absolute !important; padding: 1px 0px 0px !important; border: 0px !important; height: 1px !important; width: 1px !important; overflow: hidden !important; display: block !important;"><math xmlns="http://www.w3.org/1998/Math/MathML">K</math></span></span>가 주어졌을 때 이항 계수&nbsp;<span class="MathJax_Preview" style="color: inherit; border-radius: 0px !important;"></span><span class="MathJax_SVG" id="MathJax-Element-3-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mrow><mstyle scriptlevel=&quot;0&quot;><mrow class=&quot;MJX-TeXAtom-OPEN&quot;><mo maxsize=&quot;1.2em&quot; minsize=&quot;1.2em&quot;>(</mo></mrow></mstyle><mfrac linethickness=&quot;0&quot;><mi>N</mi><mi>K</mi></mfrac><mstyle scriptlevel=&quot;0&quot;><mrow class=&quot;MJX-TeXAtom-CLOSE&quot;><mo maxsize=&quot;1.2em&quot; minsize=&quot;1.2em&quot;>)</mo></mrow></mstyle></mrow></math>" role="presentation" style="display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; border-radius: 0px !important;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="3.591ex" height="3.278ex" viewBox="0 -1007.2 1546 1411.3" role="img" focusable="false" style="vertical-align: -0.938ex;" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#MJSZ1-28" x="0" y="-1"><path stroke-width="1" id="MJSZ1-28" d="M152 251Q152 646 388 850H416Q422 844 422 841Q422 837 403 816T357 753T302 649T255 482T236 250Q236 124 255 19T301 -147T356 -251T403 -315T422 -340Q422 -343 416 -349H388Q359 -325 332 -296T271 -213T212 -97T170 56T152 251Z"></path></use><g transform="translate(458,0)"><use transform="scale(0.707)" xlink:href="#MJMATHI-4E" x="0" y="627"><path stroke-width="1" id="MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></use><use transform="scale(0.707)" xlink:href="#MJMATHI-4B" x="0" y="-488"><path stroke-width="1" id="MJMATHI-4B" d="M285 628Q285 635 228 637Q205 637 198 638T191 647Q191 649 193 661Q199 681 203 682Q205 683 214 683H219Q260 681 355 681Q389 681 418 681T463 682T483 682Q500 682 500 674Q500 669 497 660Q496 658 496 654T495 648T493 644T490 641T486 639T479 638T470 637T456 637Q416 636 405 634T387 623L306 305Q307 305 490 449T678 597Q692 611 692 620Q692 635 667 637Q651 637 651 648Q651 650 654 662T659 677Q662 682 676 682Q680 682 711 681T791 680Q814 680 839 681T869 682Q889 682 889 672Q889 650 881 642Q878 637 862 637Q787 632 726 586Q710 576 656 534T556 455L509 418L518 396Q527 374 546 329T581 244Q656 67 661 61Q663 59 666 57Q680 47 717 46H738Q744 38 744 37T741 19Q737 6 731 0H720Q680 3 625 3Q503 3 488 0H478Q472 6 472 9T474 27Q478 40 480 43T491 46H494Q544 46 544 71Q544 75 517 141T485 216L427 354L359 301L291 248L268 155Q245 63 245 58Q245 51 253 49T303 46H334Q340 37 340 35Q340 19 333 5Q328 0 317 0Q314 0 280 1T180 2Q118 2 85 2T49 1Q31 1 31 11Q31 13 34 25Q38 41 42 43T65 46Q92 46 125 49Q139 52 144 61Q147 65 216 339T285 628Z"></path></use></g><use xlink:href="#MJSZ1-29" x="1087" y="-1"><path stroke-width="1" id="MJSZ1-29" d="M305 251Q305 -145 69 -349H56Q43 -349 39 -347T35 -338Q37 -333 60 -307T108 -239T160 -136T204 27T221 250T204 473T160 636T108 740T60 807T35 839Q35 850 50 850H56H69Q197 743 256 566Q305 425 305 251Z"></path></use></g></svg><span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; transition: none 0s ease 0s; border-radius: 0px !important; position: absolute !important; padding: 1px 0px 0px !important; border: 0px !important; height: 1px !important; width: 1px !important; overflow: hidden !important; display: block !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle scriptlevel="0"><mrow class="MJX-TeXAtom-OPEN"><mo maxsize="1.2em" minsize="1.2em">(</mo></mrow></mstyle><mfrac linethickness="0"><mi>N</mi><mi>K</mi></mfrac><mstyle scriptlevel="0"><mrow class="MJX-TeXAtom-CLOSE"><mo maxsize="1.2em" minsize="1.2em">)</mo></mrow></mstyle></mrow></math></span></span>를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.</p></div></section></div><div class="col-md-12" style="width: 970px; border-radius: 0px !important;"><section id="input" style="border-radius: 0px !important;"><div class="headline" style="margin: 10px 0px 25px; border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px !important;"><h2 style="font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-weight: normal; line-height: 33px; color: rgb(88, 95, 105); margin: 0px 0px -2px; font-size: 22px; text-shadow: none; padding-bottom: 5px; display: inline-block; border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px !important;">입력</h2></div><div id="problem_input" style="font-size: medium; line-height: 30px; border-radius: 0px !important;"><p style="margin-top: 0px; margin-bottom: 10px; color: rgb(85, 85, 85); border-radius: 0px !important;">첫째 줄에&nbsp;<span class="MathJax_Preview" style="color: inherit; border-radius: 0px !important;"></span><span class="MathJax_SVG" id="MathJax-Element-4-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>N</mi></math>" role="presentation" style="display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; border-radius: 0px !important;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="2.064ex" height="1.994ex" viewBox="0 -755.9 888.5 858.4" role="img" focusable="false" style="vertical-align: -0.238ex;" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#MJMATHI-4E" x="0" y="0"><path stroke-width="1" id="MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></use></g></svg><span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; transition: none 0s ease 0s; border-radius: 0px !important; position: absolute !important; padding: 1px 0px 0px !important; border: 0px !important; height: 1px !important; width: 1px !important; overflow: hidden !important; display: block !important;"><math xmlns="http://www.w3.org/1998/Math/MathML">N</math></span></span>과&nbsp;<span class="MathJax_Preview" style="color: inherit; border-radius: 0px !important;"></span><span class="MathJax_SVG" id="MathJax-Element-5-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>K</mi></math>" role="presentation" style="display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; border-radius: 0px !important;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="2.066ex" height="1.994ex" viewBox="0 -755.9 889.5 858.4" role="img" focusable="false" style="vertical-align: -0.238ex;" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#MJMATHI-4B" x="0" y="0"><path stroke-width="1" id="MJMATHI-4B" d="M285 628Q285 635 228 637Q205 637 198 638T191 647Q191 649 193 661Q199 681 203 682Q205 683 214 683H219Q260 681 355 681Q389 681 418 681T463 682T483 682Q500 682 500 674Q500 669 497 660Q496 658 496 654T495 648T493 644T490 641T486 639T479 638T470 637T456 637Q416 636 405 634T387 623L306 305Q307 305 490 449T678 597Q692 611 692 620Q692 635 667 637Q651 637 651 648Q651 650 654 662T659 677Q662 682 676 682Q680 682 711 681T791 680Q814 680 839 681T869 682Q889 682 889 672Q889 650 881 642Q878 637 862 637Q787 632 726 586Q710 576 656 534T556 455L509 418L518 396Q527 374 546 329T581 244Q656 67 661 61Q663 59 666 57Q680 47 717 46H738Q744 38 744 37T741 19Q737 6 731 0H720Q680 3 625 3Q503 3 488 0H478Q472 6 472 9T474 27Q478 40 480 43T491 46H494Q544 46 544 71Q544 75 517 141T485 216L427 354L359 301L291 248L268 155Q245 63 245 58Q245 51 253 49T303 46H334Q340 37 340 35Q340 19 333 5Q328 0 317 0Q314 0 280 1T180 2Q118 2 85 2T49 1Q31 1 31 11Q31 13 34 25Q38 41 42 43T65 46Q92 46 125 49Q139 52 144 61Q147 65 216 339T285 628Z"></path></use></g></svg><span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; transition: none 0s ease 0s; border-radius: 0px !important; position: absolute !important; padding: 1px 0px 0px !important; border: 0px !important; height: 1px !important; width: 1px !important; overflow: hidden !important; display: block !important;"><math xmlns="http://www.w3.org/1998/Math/MathML">K</math></span></span>가 주어진다. (1 ≤&nbsp;<span class="MathJax_Preview" style="color: inherit; border-radius: 0px !important;"></span><span class="MathJax_SVG" id="MathJax-Element-6-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>N</mi></math>" role="presentation" style="display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; border-radius: 0px !important;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="2.064ex" height="1.994ex" viewBox="0 -755.9 888.5 858.4" role="img" focusable="false" style="vertical-align: -0.238ex;" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#MJMATHI-4E" x="0" y="0"><path stroke-width="1" id="MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></use></g></svg><span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; transition: none 0s ease 0s; border-radius: 0px !important; position: absolute !important; padding: 1px 0px 0px !important; border: 0px !important; height: 1px !important; width: 1px !important; overflow: hidden !important; display: block !important;"><math xmlns="http://www.w3.org/1998/Math/MathML">N</math></span></span>&nbsp;≤ 1,000, 0 ≤&nbsp;<span class="MathJax_Preview" style="color: inherit; border-radius: 0px !important;"></span><span class="MathJax_SVG" id="MathJax-Element-7-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>K</mi></math>" role="presentation" style="display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; border-radius: 0px !important;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="2.066ex" height="1.994ex" viewBox="0 -755.9 889.5 858.4" role="img" focusable="false" style="vertical-align: -0.238ex;" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#MJMATHI-4B" x="0" y="0"><path stroke-width="1" id="MJMATHI-4B" d="M285 628Q285 635 228 637Q205 637 198 638T191 647Q191 649 193 661Q199 681 203 682Q205 683 214 683H219Q260 681 355 681Q389 681 418 681T463 682T483 682Q500 682 500 674Q500 669 497 660Q496 658 496 654T495 648T493 644T490 641T486 639T479 638T470 637T456 637Q416 636 405 634T387 623L306 305Q307 305 490 449T678 597Q692 611 692 620Q692 635 667 637Q651 637 651 648Q651 650 654 662T659 677Q662 682 676 682Q680 682 711 681T791 680Q814 680 839 681T869 682Q889 682 889 672Q889 650 881 642Q878 637 862 637Q787 632 726 586Q710 576 656 534T556 455L509 418L518 396Q527 374 546 329T581 244Q656 67 661 61Q663 59 666 57Q680 47 717 46H738Q744 38 744 37T741 19Q737 6 731 0H720Q680 3 625 3Q503 3 488 0H478Q472 6 472 9T474 27Q478 40 480 43T491 46H494Q544 46 544 71Q544 75 517 141T485 216L427 354L359 301L291 248L268 155Q245 63 245 58Q245 51 253 49T303 46H334Q340 37 340 35Q340 19 333 5Q328 0 317 0Q314 0 280 1T180 2Q118 2 85 2T49 1Q31 1 31 11Q31 13 34 25Q38 41 42 43T65 46Q92 46 125 49Q139 52 144 61Q147 65 216 339T285 628Z"></path></use></g></svg><span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; transition: none 0s ease 0s; border-radius: 0px !important; position: absolute !important; padding: 1px 0px 0px !important; border: 0px !important; height: 1px !important; width: 1px !important; overflow: hidden !important; display: block !important;"><math xmlns="http://www.w3.org/1998/Math/MathML">K</math></span></span>&nbsp;≤&nbsp;<span class="MathJax_Preview" style="color: inherit; border-radius: 0px !important;"></span><span class="MathJax_SVG" id="MathJax-Element-8-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mi>N</mi></math>" role="presentation" style="display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; border-radius: 0px !important;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="2.064ex" height="1.994ex" viewBox="0 -755.9 888.5 858.4" role="img" focusable="false" style="vertical-align: -0.238ex;" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#MJMATHI-4E" x="0" y="0"><path stroke-width="1" id="MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></use></g></svg><span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; transition: none 0s ease 0s; border-radius: 0px !important; position: absolute !important; padding: 1px 0px 0px !important; border: 0px !important; height: 1px !important; width: 1px !important; overflow: hidden !important; display: block !important;"><math xmlns="http://www.w3.org/1998/Math/MathML">N</math></span></span>)</p></div></section></div><div class="col-md-12" style="width: 970px; border-radius: 0px !important;"><section id="output" style="border-radius: 0px !important;"><div class="headline" style="margin: 10px 0px 25px; border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px !important;"><h2 style="font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-weight: normal; line-height: 33px; color: rgb(88, 95, 105); margin: 0px 0px -2px; font-size: 22px; text-shadow: none; padding-bottom: 5px; display: inline-block; border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px !important;">출력</h2></div><div id="problem_output" style="font-size: medium; line-height: 30px; border-radius: 0px !important;"><p style="margin-top: 0px; margin-bottom: 10px; color: rgb(85, 85, 85); border-radius: 0px !important;">&nbsp;<span class="MathJax_Preview" style="color: inherit; border-radius: 0px !important;"></span><span class="MathJax_SVG" id="MathJax-Element-9-Frame" tabindex="0" data-mathml="<math xmlns=&quot;http://www.w3.org/1998/Math/MathML&quot;><mrow><mstyle scriptlevel=&quot;0&quot;><mrow class=&quot;MJX-TeXAtom-OPEN&quot;><mo maxsize=&quot;1.2em&quot; minsize=&quot;1.2em&quot;>(</mo></mrow></mstyle><mfrac linethickness=&quot;0&quot;><mi>N</mi><mi>K</mi></mfrac><mstyle scriptlevel=&quot;0&quot;><mrow class=&quot;MJX-TeXAtom-CLOSE&quot;><mo maxsize=&quot;1.2em&quot; minsize=&quot;1.2em&quot;>)</mo></mrow></mstyle></mrow></math>" role="presentation" style="display: inline-block; line-height: normal; font-size: 14.4px; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; border-radius: 0px !important;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="3.591ex" height="3.278ex" viewBox="0 -1007.2 1546 1411.3" role="img" focusable="false" style="vertical-align: -0.938ex;" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#MJSZ1-28" x="0" y="-1"><path stroke-width="1" id="MJSZ1-28" d="M152 251Q152 646 388 850H416Q422 844 422 841Q422 837 403 816T357 753T302 649T255 482T236 250Q236 124 255 19T301 -147T356 -251T403 -315T422 -340Q422 -343 416 -349H388Q359 -325 332 -296T271 -213T212 -97T170 56T152 251Z"></path></use><g transform="translate(458,0)"><use transform="scale(0.707)" xlink:href="#MJMATHI-4E" x="0" y="627"><path stroke-width="1" id="MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></use><use transform="scale(0.707)" xlink:href="#MJMATHI-4B" x="0" y="-488"><path stroke-width="1" id="MJMATHI-4B" d="M285 628Q285 635 228 637Q205 637 198 638T191 647Q191 649 193 661Q199 681 203 682Q205 683 214 683H219Q260 681 355 681Q389 681 418 681T463 682T483 682Q500 682 500 674Q500 669 497 660Q496 658 496 654T495 648T493 644T490 641T486 639T479 638T470 637T456 637Q416 636 405 634T387 623L306 305Q307 305 490 449T678 597Q692 611 692 620Q692 635 667 637Q651 637 651 648Q651 650 654 662T659 677Q662 682 676 682Q680 682 711 681T791 680Q814 680 839 681T869 682Q889 682 889 672Q889 650 881 642Q878 637 862 637Q787 632 726 586Q710 576 656 534T556 455L509 418L518 396Q527 374 546 329T581 244Q656 67 661 61Q663 59 666 57Q680 47 717 46H738Q744 38 744 37T741 19Q737 6 731 0H720Q680 3 625 3Q503 3 488 0H478Q472 6 472 9T474 27Q478 40 480 43T491 46H494Q544 46 544 71Q544 75 517 141T485 216L427 354L359 301L291 248L268 155Q245 63 245 58Q245 51 253 49T303 46H334Q340 37 340 35Q340 19 333 5Q328 0 317 0Q314 0 280 1T180 2Q118 2 85 2T49 1Q31 1 31 11Q31 13 34 25Q38 41 42 43T65 46Q92 46 125 49Q139 52 144 61Q147 65 216 339T285 628Z"></path></use></g><use xlink:href="#MJSZ1-29" x="1087" y="-1"><path stroke-width="1" id="MJSZ1-29" d="M305 251Q305 -145 69 -349H56Q43 -349 39 -347T35 -338Q37 -333 60 -307T108 -239T160 -136T204 27T221 250T204 473T160 636T108 740T60 807T35 839Q35 850 50 850H56H69Q197 743 256 566Q305 425 305 251Z"></path></use></g></svg><span class="MJX_Assistive_MathML" role="presentation" style="top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); user-select: none; transition: none 0s ease 0s; border-radius: 0px !important; position: absolute !important; padding: 1px 0px 0px !important; border: 0px !important; height: 1px !important; width: 1px !important; overflow: hidden !important; display: block !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mstyle scriptlevel="0"><mrow class="MJX-TeXAtom-OPEN"><mo maxsize="1.2em" minsize="1.2em">(</mo></mrow></mstyle><mfrac linethickness="0"><mi>N</mi><mi>K</mi></mfrac><mstyle scriptlevel="0"><mrow class="MJX-TeXAtom-CLOSE"><mo maxsize="1.2em" minsize="1.2em">)</mo></mrow></mstyle></mrow></math></span></span>를 10,007로 나눈 나머지를&nbsp;출력한다.</p></div></section></div><div class="col-md-12" style="width: 970px; border-radius: 0px !important;"><div class="row" style="border-radius: 0px !important;"><div class="col-md-6" style="width: 485px; border-radius: 0px !important;"><section id="sampleinput1" style="border-radius: 0px !important;"><div class="headline" style="margin: 10px 0px 25px; border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px !important;"><h2 style="font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-weight: normal; line-height: 33px; color: rgb(88, 95, 105); margin: 0px 0px -2px; font-size: 22px; text-shadow: none; padding-bottom: 5px; display: inline-block; border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px !important;">예제 입력 1&nbsp;<button type="button" class="btn btn-link copy-button" data-clipboard-target="#sample-input-1" style="font-weight: 400; line-height: 1.42857; font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; color: rgb(66, 139, 202); text-transform: none; padding: 0px; outline: 0px !important;">복사</button></h2></div><pre class="sampledata" id="sample-input-1" style="border-radius: 5px; overflow-x: scroll; font-family: Menlo, Monaco, &quot;Source Code Pro&quot;, consolas, monospace; font-size: 18px; padding: 8px; line-height: 1.42857; word-break: normal; overflow-wrap: normal; background-color: rgb(247, 247, 249); border-color: rgb(225, 225, 232);">5 2
</pre></section></div><div class="col-md-6" style="width: 485px; border-radius: 0px !important;"><section id="sampleoutput1" style="border-radius: 0px !important;"><div class="headline" style="margin: 10px 0px 25px; border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px !important;"><h2 style="font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-weight: normal; line-height: 33px; color: rgb(88, 95, 105); margin: 0px 0px -2px; font-size: 22px; text-shadow: none; padding-bottom: 5px; display: inline-block; border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px !important;">예제 출력 1&nbsp;<button type="button" class="btn btn-link copy-button" data-clipboard-target="#sample-output-1" style="font-weight: 400; line-height: 1.42857; font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; color: rgb(66, 139, 202); text-transform: none; padding: 0px; outline: 0px !important;">복사</button></h2></div><pre class="sampledata" id="sample-output-1" style="border-radius: 5px; overflow-x: scroll; font-family: Menlo, Monaco, &quot;Source Code Pro&quot;, consolas, monospace; font-size: 18px; padding: 8px; line-height: 1.42857; word-break: normal; overflow-wrap: normal; background-color: rgb(247, 247, 249); border-color: rgb(225, 225, 232);">10
</pre></section></div></div></div><div class="col-md-12" style="width: 970px; border-radius: 0px !important;"></div></div><div class="col-md-12" style="width: 970px; color: rgb(51, 51, 51); font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-size: 13px; border-radius: 0px !important;"><section id="source" style="border-radius: 0px !important;"><div class="headline" style="margin: 10px 0px 25px; border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px !important;"><h2 style="font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-weight: normal; line-height: 33px; color: rgb(88, 95, 105); margin: 0px 0px -2px; font-size: 22px; text-shadow: none; padding-bottom: 5px; display: inline-block; border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px !important;">출처</h2></div><ul style="border-radius: 0px !important;"><li style="color: rgb(85, 85, 85); border-radius: 0px !important;">데이터를 추가한 사람:&nbsp;<a href="https://www.acmicpc.net/user/BaaaaaaaaaaarkingDog" style="background-image: initial; background-position: 0px 0px; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; color: rgb(85, 85, 85); border-radius: 0px !important; outline: 0px !important;">BaaaaaaaaaaarkingDog</a></li><li style="color: rgb(85, 85, 85); border-radius: 0px !important;">문제를 만든 사람:&nbsp;<a href="https://www.acmicpc.net/user/baekjoon" style="background-image: initial; background-position: 0px 0px; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; color: rgb(85, 85, 85); border-radius: 0px !important; outline: 0px !important;">baekjoon</a></li></ul></section></div><div class="col-md-12" style="width: 970px; color: rgb(51, 51, 51); font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-size: 13px; border-radius: 0px !important;"><section id="problem_tags" style="border-radius: 0px !important;"><div class="headline" style="margin: 10px 0px 25px; border-bottom: 1px dotted rgb(228, 233, 240); border-radius: 0px !important;"><h2 style="font-family: &quot;Open Sans&quot;, &quot;Helvetica Neue&quot;, Helvetica, Arial, &quot;Apple SD Gothic Neo&quot;, &quot;Noto Sans CJK KR&quot;, &quot;Noto Sans KR&quot;, 나눔바른고딕, 나눔고딕, NanumGothic, 맑은고딕, &quot;Malgun Gothic&quot;, &quot;Nanum Gothic&quot;, sans-serif; font-weight: normal; line-height: 33px; color: rgb(88, 95, 105); margin: 0px 0px -2px; font-size: 22px; text-shadow: none; padding-bottom: 5px; display: inline-block; border-bottom: 2px solid rgb(0, 118, 192); border-radius: 0px !important;">알고리즘 분류</h2></div><p style="margin-top: 0px; margin-bottom: 10px; color: rgb(85, 85, 85); border-radius: 0px !important;"></p><div class="spoiler" style="border-radius: 0px !important;"><ul class="spoiler-list" style="border-radius: 0px !important;"><li style="color: rgb(85, 85, 85); border-radius: 0px !important;"><a href="https://www.acmicpc.net/problem/tag/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D" class="spoiler-link" style="background-image: initial; background-position: 0px 0px; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; color: rgb(85, 85, 85); border-radius: 0px !important; outline: 0px !important;">다이나믹 프로그래밍</a></li></ul></div></section></div><h3><br></h3><h3>풀이&nbsp;</h3><p><img src="/system/uploads/images/000/001/469/original/image.png?1537897870" style="width: 428px;"></p><p>위와 같은 형태의 식으로 이항 계수를 구할 수 있습니다. (출처 : 위키백과)&nbsp;<br>하지만 곱으로 구하면 수가 너무 커서 int 형이나 long long 형태의 오버플로우가 일어납니다.&nbsp;</p><p>이와 같은 경우에서는 dp 를 이용하여 풀면 쉽게 풀 수 있습니다.&nbsp;</p><p><img src="http://hellogohn.com/system/uploads/images/000/001/468/original/image.png?1537897825" style="width: 338px;"><br></p><p>이항 계수는 위와 같은 형태로 규칙을 이용하여 구할 수 있습니다.&nbsp;<br>이미지 출처 :&nbsp;<a href="https://samtoring.com/qstn/QST0026495.png">https://samtoring.com/qstn/QST0026495.png</a>&nbsp;</p><p><img src="http://hellogohn.com/system/uploads/images/000/001/470/original/image.png?1537897893" style="width: 642px;"></p><p>위와 같은 항등식을 이용하여 구할 수 있습니다. (출처 : 위키백과)</p><p>자세한 풀이는 소스코드를 참조해주세요~</p><p><img src="/system/uploads/images/000/001/471/original/image.png?1537898056" style="width: 333px;"></p><p>+ 5와 2를 입력하여 dp 배열을 살펴보면 위와 같은 모습을 가지고 있는 것을 확인할 수 있습니다.&nbsp;</p><h3>소스코드</h3><div class="colorscripter-code" style="color:#FFFFFF; font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace !important; position:relative !important; overflow:auto"><table class="colorscripter-code-table" style="margin:0; padding:0; border:none; background-color:#1E1E1E; border-radius:4px;" cellspacing="0" cellpadding="0"><tbody><tr><td style="padding:6px; border-right:2px solid #4f4f4f"><div style="margin: 0px; padding: 0px; word-break: normal; text-align: right; color: rgb(170, 170, 170); line-height: 130%;"><div style="line-height:130%">1</div><div style="line-height:130%">2</div><div style="line-height:130%">3</div><div style="line-height:130%">4</div><div style="line-height:130%">5</div><div style="line-height:130%">6</div><div style="line-height:130%">7</div><div style="line-height:130%">8</div><div style="line-height:130%">9</div><div style="line-height:130%">10</div><div style="line-height:130%">11</div><div style="line-height:130%">12</div><div style="line-height:130%">13</div><div style="line-height:130%">14</div><div style="line-height:130%">15</div><div style="line-height:130%">16</div><div style="line-height:130%">17</div><div style="line-height:130%">18</div><div style="line-height:130%">19</div><div style="line-height:130%">20</div></div></td><td style="padding-top: 6px; padding-bottom: 6px;"><div style="margin: 0px; padding: 0px; line-height: 130%;"><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#4EC9B0">#include</span>&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">&lt;</span>iostream<span style="color:#FF3399"></span><span style="color:#569CD6">&gt;</span></div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#569CD6">using</span>&nbsp;<span style="color:#569CD6">namespace</span>&nbsp;<span style="color:#DCDCDC">std</span>;&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#4EC9B0">#define</span>&nbsp;DIV_NUM&nbsp;10007</div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#4EC9B0">#define</span>&nbsp;NK_MAX&nbsp;1000&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">+</span>&nbsp;1&nbsp;</div><div style="padding:0 6px; white-space:pre; line-height:130%"><span style="color:#DCDCDC">int</span>&nbsp;main()&nbsp;{</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#DCDCDC">int</span>&nbsp;N,&nbsp;K;&nbsp;<span style="color:#DCDCDC">scanf</span>(<span style="color:#E3A25C">"%d&nbsp;%d"</span>,&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">&amp;</span>N,&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">&amp;</span>K);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#DCDCDC">int</span>&nbsp;dp[NK_MAX][NK_MAX]&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">=</span>&nbsp;{&nbsp;0&nbsp;};</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#57A64A">//&nbsp;for&nbsp;문을&nbsp;이용하여&nbsp;n이&nbsp;1일때부터&nbsp;갱신합니다.</span></div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#57A64A">//&nbsp;각&nbsp;라운드에서는&nbsp;k가&nbsp;0~n&nbsp;가지일&nbsp;때를&nbsp;갱신합니다.</span></div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#569CD6">for</span>(<span style="color:#DCDCDC">int</span>&nbsp;n_row&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">=</span>&nbsp;1;&nbsp;n_row&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">&lt;</span><span style="color:#FF3399"></span><span style="color:#569CD6">=</span>&nbsp;N;&nbsp;n_row<span style="color:#FF3399"></span><span style="color:#569CD6">+</span><span style="color:#FF3399"></span><span style="color:#569CD6">+</span>){</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#569CD6">for</span>&nbsp;(<span style="color:#DCDCDC">int</span>&nbsp;k_col&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">=</span>&nbsp;0;&nbsp;k_col&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">&lt;</span><span style="color:#FF3399"></span><span style="color:#569CD6">=</span>&nbsp;N;&nbsp;k_col<span style="color:#FF3399"></span><span style="color:#569CD6">+</span><span style="color:#FF3399"></span><span style="color:#569CD6">+</span>)&nbsp;{</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#569CD6">if</span>&nbsp;(n_row&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">=</span><span style="color:#FF3399"></span><span style="color:#569CD6">=</span>&nbsp;k_col&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">|</span><span style="color:#FF3399"></span><span style="color:#569CD6">|</span>&nbsp;k_col&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">=</span><span style="color:#FF3399"></span><span style="color:#569CD6">=</span>&nbsp;0)&nbsp;{</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[n_row][k_col]&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">=</span>&nbsp;1;&nbsp;<span style="color:#569CD6">continue</span>;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[n_row][k_col]&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">=</span>&nbsp;(dp[n_row&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">-</span>&nbsp;1][k_col]&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">+</span>&nbsp;dp[n_row&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">-</span>&nbsp;1][k_col&nbsp;<span style="color:#FF3399"></span><span style="color:#569CD6">-</span>&nbsp;1])&nbsp;%&nbsp;DIV_NUM;</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;}</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#DCDCDC">printf</span>(<span style="color:#E3A25C">"%d"</span>,&nbsp;dp[N][K]);</div><div style="padding:0 6px; white-space:pre; line-height:130%">&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#569CD6">return</span>&nbsp;0;</div><div style="padding:0 6px; white-space:pre; line-height:130%">}</div></div><div style="text-align:right; margin-top:-13px; margin-right:5px; font-size:9px; font-style:italic"><a href="http://colorscripter.com/info#e" target="_blank" style="color: rgb(79, 79, 79);">Colored by Color Scripter</a></div></td><td style="vertical-align: bottom; padding-right: 2px; padding-bottom: 4px;"><a href="http://colorscripter.com/info#e" target="_blank" style="color: white;"><span style="font-size: 9px; word-break: normal; background-color: rgb(79, 79, 79); border-radius: 10px; padding: 1px;">cs</span></a></td></tr></tbody></table></div>
You can’t perform that action at this time.