본문 바로가기
학부공부/Java_Basic

Chapter 18. Recursion(1)[Java Basic]

by sonpang 2021. 11. 6.
반응형

18.A - Factorial

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

10.9절에서 소개된 BigInteger 클래스를 이용하면 큰 숫자에 대한 팩토리얼을 구할 수 있다 (이를테면, 100!). 팩토리얼 함수를 재귀호출을 이용해서 구현하시오. (그러나, 단순 재귀 호출로는 fail. 메모화를 활용)

Using the BigInteger class introduced in Section 10.9, you can find the factorial for a large number (e.g., 100!). Implement the factorial method using recursion. Write a program that prompts the user to enter an integer and displays its factorial.

 

INPUT

* Line 1 :  테스트 케이스 T (1~10)

* Line 2 ~ T+1 : n (1~10000)

 

OUTPUT

* 1~T : n!

 

SAMPLE CODE

import java.math.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        input.nextLine();
        for(int i=0; i<T; i++){
            String numberString = input.nextLine();
            BigInteger bigNumber = new BigInteger(numberString);
            System.out.println(factorial(bigNumber));
        }
	}

	YOUR_CODE
}

 

SAMPLE INPUT

3 982 1545 6215

 

SAMPLE OUTPUT

469334317148140749406216870023560953789663822582271786299082889560691696445697736463821802727779314513374790647293188217378707774562420864093777845401759818042912689948164964965995287226497726220071245527064879140348338375599217212380324258834313929901107986429302630808956042118313325315001764013959815219122259665863945336494074249282300466718302998900231276347656536940354217005805841560061199723456138056217059972902654750275093419369145780426261563747423944125447207001852418310116482841716472049404993455323879061996844384482163973453328875145175175828673242223055553083128205142506556761591161703380354266996133570370455764379981525291662707763457956839134829681191257375699147694255944136333556337688982770495144778355408823751312515977384385838176470285722114989109587562075217818758072839993809127937431593362578071758228050785841944337650209819856288052980765171609046124534746883534293354732607995850174590148759941498532551648137953064189066965669809578687751794669681425760676619196653370063406147828637124532652849161554887146427359166851098603214466843092837349084782609389958692942742935511665596677304967968948852525771020356172041830534631985565843936616746389029853784839463051273299778608137072645564377416853947286086004921617751894535081393895594242648748377360869658851466759476809418457989016444441885480409097871637092484831224722379522218568104986531090024756343963080505537926908574224751880431743969593685650121402395829216589540588767031722800156650816793054478128935323157771034868255256968906202160019828177697993102847702977562246570386643204145997951843434766395367992026522219190849841438075992353680649253993883553363282744843231360881003422640043976538588382690846225686000185484163260675151356457418229864589253499218145376640126850816974398767134971510630899128320567231809590890081562010430596997228832398634482504368631792690477895513164004547039775617047324383362411865085658659889361543004097754433808531919944082619735934646391531879752232712074362412039396208972419949902958482421062347219435719674847788108002254791523069424007929462617592730724638222228045572209501867447271795330690912572107972385102431352086804240832150290450574543195707122716957539051835525444324769999798764167163313910943552253493490492249610983047168000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 8000377334273947734117443819851025921792659710000122064176440286787261948640171562194018750653137957677543860591065069093955258074072090240945991175066525076352651851733230477022578878263163053006959554620820234426877244678049274479262665752274333734737304850462693658221404837312737627840500493719509929502716556775833280687551715827451691900233061635492146196401105908781161718491701470043622081021519770122212391661579750188761829071472026586182770686819086918018920477221334012491570802824439976845027826375179950201488045636463565501026490193965395139784126299994516474118161976152989531591838801855275539193173054374236300790330945635400585336638734380292286308189401326715175414999973547424014631524480822126398550112872185507898738249051103102228029050283038657984965514779081392234128854409055457852914009960799682755083775358949394596643822966410584191376978557049619380273254868271075608413781577734500549886834536644725361209427042406747989607871349750915886607260855431839973563262895547464107283149943309419912487226538995575277008047494337447786699166926689048137317788477265067797975177143636398059651982868355465009826272055466963136756469203718906431556639338974186790959848446969731613956163456453246056403229981926739629612609461050137814351115988484663672535136882964032734659175553571174899213309957700548579804994733801049001941998859928045598019682260332349901979816150153633300298635598208774490564022651420355129307863079829467599100626933068312404366407565341237875454648832943075781483199555071013853154799864675788738760181509543440865660991431543727520466396393581877293862854456951546571294154402464841305683670886491786336081229532448025622790043046694867988300737665032452204611617199353764397814839903626529870225507318000067048463455439777657249566442981221581266659636356682788764575346868759404577119975541835833877290165822488305184571124426415006279994240155941501339098031580054612496610680617269878322277157415592704132007475386472809107361656113837146135435927582773394170236927310622009529061839730734051324383653091095332224872404786932421403803753147130901972879825453316203140379555479900267956153257698875415711670245231540284260231056074830693626462689782729839596292156337906432941513715088567034977263979622900543502913454082971494142466430115373982620421058516069368576544144379587433823436446749912800712223427189503511486510482205383995975256819702776978119964112916029729683276203109606192988572757899498196383826303978852848583612500093285171850939819201684317174713464677126237807051826359159029994704631877980530115517147813781213536290681996448462227377652904919960297935365397466918079990634644892603454187759423708935415817918331579527159093129612515714491068746996823521722404021629298950168925332138811026918030112127176918270724069407762578417168676463194074657257956893915130547387777058254292454406889591310225450970646929568908282673514789865707027366559757530359729839241277332382756816831202400593893172360527345939702844808180938450296199686661546751886356448230434702179712037984265840419487924692460952670325149413655080262348529379641258750004062373902668452067156390593087844340186724206028089128037855599882273234354990412720160762665461846499039216769391887329862825189036910840430514341906940550334290946631202028527986597929638394126912540070186227617422442459242104652736888452913953433345395441490012841816059294646327692696769561146854564575004169978797860057013807754777335949935118802015427175514595003900726519820463660837399134606155792485422184248744007050299226679579712362203453003519504139154909082384611417520803841463131324610129599721360929308411704537674400552354720392435499541113765932779691859585016108640351936856125672506439839560761558341288872199291218216127304267232973462129205469217169968070254520968978182456146658772668085302367433816333170840685125952907549586023776256000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 246747494413438651961798341410478513165728687971840842388909092631184889108601402676169553822473219007299445101085491909419365767583476642631765506136463451860112267675889818239818584010453666386807194464528157286193473158663676107952249721933068902272872598723307111539919284922421247357755181764916834494680197749384642929042191885992150353969862801935171914830855803940225143615500608386742367088295659939535550026605997907364850575475472607861048344079050482491955450292123719561179479371607112471245382546732798455398315291266811033888054458127224190881787601187871866239038549572434764568521652354211989839149263119479829256212103879118637371075662672712842043977113856252071612140224590297359066578281203043158136273854691096463258555656828120464908296466407923194486666530374691908060729814632917317740633111395914636375315429548643779010565239793773312409896673934944512343246375413158588643436911989505170419436045587706462340768754488248006140427226102065074852898209767502750902168968648613365154749773060487820136680998613755440770976128773921394075324776454571307658694061872036398104435713217005507495525875575626722523507968055518613360437258769513812731416480384918730921320723885058866686226457928715624885698310607076010590698729593422646210621753482753375764617990733813343893902190541127721608015820623284127121422340913407521994239408466304155024822906471595803460709687823521468740643273934389802569318889206319470008854111382092568138728735939204776035566811996214145317994137322336806280152760003471992299600092671207585194854932454765275363603497853465034681642520694881555790364893648560994677639618041718511373337396448800595464905862595906019418938283238143790308709491629084520999652708092396889846650549892426543976496869638584891640527795852862664836921412228521095124862857722030363200488969752802632433904571586966470839577507877672332380418261586138303296494577057059974685975463762900421637823825048708964340409177090786312555348235237950465996748714386038744315531500516637204208600979198906079598404702651829800447364491032814922069931495846624416853511795253562024395542666106795787605060224822661354267813418316354795023696301638498241106774694458630505093238989546613716445287987693293565164093669988341251676448504782854466691241042348739868259255855708444191395732728509866470732269511478638415535504233455876148984663903827193056327958796676395631432176409260586653231393383459378155478314477678529066856496172295009237200680358431759149334491296929561226119864715511739770143502161518256370389085401695204902134520452546023519046104150309442144943454605193352071698109702149843809737247341963865179553557487269751946708347984864344931027259394884614248078834648982249104371690852938826194909061886316996610656619542947122060975867747217280746130112573544562742038408541382364725319254373084852171331363477303428517515449305631881518565187765292299822862750153588198299425524480979631393387167108644854298632954336535586653752692211219203320225951977127946314045796695982792743383024997921187154795073667812279200427062740354835034703348780671757981563476425749553589390380215344596487287579105402002673264168680179260573759688889185942840281610486078059678773675476215341435126259093422608948641590071482750893796214013293586223137982890055750091137761756814401135650898249683901419578334732927864164281943997434052649801244199405098962596251195665782376313886260667394481770747475780553162081670804414150628604169707204108179469786991873618294049073696891435172063613407332568830977884422112264140485704382048013461767199122976827946382984448661789476701921347098685169590502292649586524149866342656531423859904957584686861727159738983127276042241479299537891603746447596858999013102023170648049975308381187962910463469629840666723448751281037710798059202780519914530004840403496200404389599297237670991292518027708698830020855704063324644922633985794558276110664737669558379836774382072968499338615577639909532747787222891046760143626051764196505851251328765512181402126752419118607246553410959253945766125826604761887862114256390401734419474810254091163859995690250510827984621991895590708783763697584000301126629632018037854520483959933975165969293136063631787598471793166838563415309127187348281963692728105572390907296218895512369754964463207223997189601087949336706165224758355742064443686152773289965711818610231670299780668996406868228020122744588677837394464587858871253084605832118033386466174239798091211632308422831480890860013318269344924430196181231571330022168177853667937936421783858375099089984122965598972415307207977801679052278332066695899811812755984311700373975507456822177605910927226234198313740712099635971165219606707755924198256960374671538912861983034213435717717893978834574348018218725889435095687385939187678505714006119580755018877938549199159156047058304248854618202153919332876717146921568482829638077826574307878081091234893210699717483841828438336715375356283541483205901404963568672902334238498234181516594497004311552393987907777250704027858054765525925587329977513459105062272898583194717984345267837270273952155222075322198946932996233128714809468084248532372137469106099102015108535347718824266025528061214147009217300034977281027713250817664137048278077263710737223670098136471170368157436152951957886047233988761992286067904869510237097806736915710568301348116069214511275382441063661313054644640017014874383743465747922184479105948018948384231074769117502242006349673823143371160800324108578608267727212148342793583904254420991235840570424529442617148516738383194709199372432685189682073032691288621259553539379020348490732860417859712244433051229739674587147896247392395709774537389833598577295713765326498149329858422691677909727508229986928125456900299711803773392720073449778183511480764478281467131119812117103165945084390583038806116121492663874439139474965781102429761766964378659275878944076931110774653806392885917176784614487960499900626816304203776405345068898675580902906690398272954749942399596064932730484528484575738498520925551297633085203159832712808307062115638960280747380720564357292712574357089599046258499615442824599238784483892626546270414517630421746413754341037372986464201316505435400681802308183989704949148723943373245817455291660783215882671848883368216603666600403379826747457304800395232479762938390221587261265854942544856141691635576775405646818755217519262009294136678580218482657806375231873525807110487277158675877690706626977492360302116573443154062520396986546930805658080978619568577906964815194269749685813871845943417434958412604296030904171771927414214940245533969815333842616755792670166942007931512671375826067549601674178213288864205831740890288295747098665196812047790653990925115777192075917761420023051805086304047895758039943890964006928409006250278247795842563744792653420153044735446844482874614966775779116417798369208860871383901159289854921882029869877997985626375159426706173352222335157529399818594913416833152522829108199462919527222662245799944899600410318556171129427343467848373646436825340137082098853137486315585814204905438381988182083638840780347456361636739783452016050850774507187322923743958636751065329384556259284651117491622754517740396614480537076694262255893995182826105604458645117299409013455234278133627325942373552993361094008535773890252445590430108525206988211668348360446829353293935663766321316125980829288428969400838915959049389041130751914374980374378144114207630384801354875021298031117363272257616385644300085989430119600255589241215373639451272149177758077320016950405773000258485138810293128251572635322288468237431549999239134372135778081562778956597265678372229904369036350046146259569946798744286646537745669398272646564602132960540051748815073045916974919964569011395629761041355195698511934562414015875738807985138245604340823986008465177205434972437451499685533319087579163854739825581909928899240153872197811247792595862588873121872910090704138934668849768792330927147654126429793287414868675502131801864955213267189749917229301235368347420533835617106820562946142491976525856955533204354213193037160195504398863502091377723354140938400296718880845220728984712267761490281023549669185720995836144767839735793145382537990361772534008756141704822525004262898844453050775942956020916298085420840165814854930928174275401734292576717192481233524717197022260777717068513699712315248411689938736826068119072362880757094910955518550319266125932014354378037414029642394482392813388198889571598260196111343921532794693240955614566345760238295527564903824180712130709672070459187467900212342707706715613610405250745635289150176882885774901699056886321549796484878977241172890773331231907889403529015632905344812450810419253532522474338046041821635806606827563164913547161066815925880623375565694419958427150663963774504267081081592309328268944832870684439459181647645203786879697639865796356434681258141564029749944094997141038299752580084454198447756130626558942808673259712335150209623482026882059125209212895504150413414579408174610139409295754444715073134590191765948976305268809021424689168884465318805040553058918469493957488463298318781240279359589496807092109137146386065288636816614743256098332133337167578404184504379896954397540818983371513011929561493442288605518951663566842515043382438402081476218149435180473740838551198021670866039144734762633730406336670364945130781208348169433499775650865956103436677459135521334131409206657474911237469954139991850730488452319124698701611842553492040415116793731928046927131342710999225957894921397716163391409118127684505643453768847084801493577464003530931066743337441879368335577527856940892126394116709021282892537688797674976077461130688586077345219274017832867889877191303659435099195775264679283073026742779669485410417210348822587742955890113521910183438518765375809146458033605116630822800997644632788112303493271570477507773426689659047243800924714315192205665934355658969637107561700154048844309827129541768508720456512225053038576365808910062733397614978909338751754130700740805382143396069627175990343548780555305789500828061275699879603587089063332959032448424438988494172229566961158671645957661526654519584341042383280824010947565615087620141842506554394261808938968641487437021677017207952876524728335677683743234148246069012523987370227568523408771703392951055403594954279864257831255840563201199396934313909648724325398177278196991361771274445162291453967343844835313314956802499703765418560116538186194534894209996630906533086448410459160400794117046588648080356208699064939398417415762943997900249900414275984966889511555745649803790385784816377061097460323455512437398292535786064834329368255059557379614943689694162723104672730715945157592659076014742017211096089446176627828622754726709154789928520340386307976890236087730377483356344481444186784218469669657213811070091102806885814995707522673696777975858228889058998533616545726250823842194465515088314848587331259126199332573931995725012124596660599072096349430180275021667671598432964357253395664275680150106846807147749319144450906225988842850790093868231796356977759012726032728143960589865197426497600606377288271396599819936520165769556795912445382689995249094743643267762929787973976034778467633824852037838977617480113559236770026659521385721319454162105976235684884970438213194028448000601089417157903309683089162583875647411825125103055913811679815537174750487002909530171510511396646426229745614121359479227055560587397039257059961790829906613504135231460437418009105562812532608642995856766973007146101800600545414025837791734480707778145480084004250299818082524364796548869527650189195465867529552175498671467783511760521382930098919707248206149792609519381460179231220352946433875154110275282319871496655768141924104763720017863096240292553215715148182734702934304323044518905450813982664435462734727892442185064250846188632870039970319168521336720869675884841310701149797817595487508446765748246703722282061395605680602503734653728237954203885378430448838686543651440008004903014366666093517819396821806918596829625312190740913001982464302859480294363658356258985986493144613362473380786947170717328024871459276271664166164869304445100051330859959362471232393832804876537267083098772564763624651238325036886458217433458369055519432305388509978106781118787149020637224865844768674780191104918802796711554591544214587667035979551663167202287490133271395906728382150851184321367387460466140485060487679413625902012143252088024285429795050953300140125214804363573321661205160782282161366190470818670414115449349385898486722664095270954856343601619578855840625132274978616740941538125955852766867210211713762291350497245347705502777643053492075151773185318904776324661979463298509083685138745357294751069359365194722179045030596134825227885648823400304178259361966100403774186757332831610871569450891992090260881906708879587355134738290939425570855150468430878377023050108615665579673867500900966659436777554367236399493531073084496691747537064816170732035791574467067954298668894541458493052930472253953751435807687839004530238202221997521886589750634396589955239691729917392119029082516040894063837696223399464534445797765136120602182207123458624657802810209729757079317517328644845810250796959234884023175569891066973905014425226904895423718218507551360124949405477013954608556346732232273153617211960803578229502872160918577463803170069981518528412452715268469763409959375524302065542520060107727964096724179335843876684318855345440370300442378786278316178016020953147003099858154870675770681276034736842851806247240984156778569559685979371020919540348487491613072059714597135263180865915954193646312408959644530665619427575723337265748557798061028870435400010139865903933010491828970997078059423779795637227276313232094927639684407497391489967177851588892295610354858813627243628832687576649702578515190149341264258775936793347746072267113908341706766236238348147466962156754096666846871257342883918992665559433275939647081530779189607790452155320706248253322452070315967579567783155654970970937077066068367779592178861844130538470263660758669017497349275449495138081820387700076375412719121737931983184397827645848337879450329423760230850785337944499700323863654722391796324255027316353942333574552526601066276050046580909540146564747193688340261157573199185934668109395157495598873316010675718651807935321807099565814807094307457913588884743432046369693217591162922971812725074264770063481503205752326866221869471116223039849418940318061005077396737077888840857774298899978286453706114441352071465775315110041633528131919449766657956719199611329617404223887618937016024120556603925397233323482691666855376793091207553423011641906966494822217855245542925950401689288681419247976172538248445861482659543986822559921928816783263815808122310989609907499716040789055259435790101205439910370997949836362114094839335345486954106959137670401352135415960478929594116367602594678699447109324062809300315844721267870033024567157843485244414315352892237029175315697368290577119216813783571993421906516181978930607829285160868296228897307272051902187660975919974085945140339167549945595113618469419041782284039463784149273014737821355255357950597929643438605958401308680623735815016673680542628798176959572715570357386884994038258320526787092889611313511774035001860350489181301744888678902664844695321650809100659913707230706904533196127231668401334480244319119460390668480757970685152413673873308844940782643088217031933928307860326359215963028010072234894705181220437640112591208011565412722810292027198766582193182249054747982954260512920888763616017221804591032191802203116479257678902536826211512226750875122061460577311189192542714169360836155501489618287722225640805754919731878972678828781821342517436039735873989067390420619260137527048173208760338883698582112734835111315133513344808590896514514486938494543795841533987935351642812356286132552711621560129612440348462367250780976515342753923443377878874287508017955480962620786559033214763723950196192048279182135488535753423600569872958359281170095431364997299998730390703734401976926067589017602383810912359298742393634532796660821464490949563216602381789391813187369166522747692689881880105125464256550669962817252964430968405689586767778718705032799419275724213941438192566866970216516635470780839144840667271726952864277226197872393787315989573241161271537273814771762547745381894987921332707682863347273893943423694149968852057216903210826140578639084179316682675094869155361135731369230618486134495909095050831369648771733550248385894789134710236738242233009712517297172001661036744347672229768575861109256410877237112564386072880554870898966774149037962661293557931376357667948173383716019748791785974291339864075891898250096805001992960658103473194647832425225639198886216726721211081907648444834083117891796523728138676375489626058516081610784180547932318928471395001583533088763895515441854274797297370694132331013416799269362427873545359645495458225617461069102786276865012014223970650260479191274604374183374141153498121727519468865150548552274722696206007634229809512222382861843817280279736234377482527335392984754717934469793352771362737146490981846260565375952488303841047694695001756796509013977156145101059003200750358230758395725765667088226462576457551169281580468621743027417435949358627186967241598472067042733183151140289099367940092084675896651503974470032353804611986969327220158651383851299647421752188514083209318664285774469271920170072241996937011002825613173216702151649999611341233407641361623399027409663516081284302893203967901643524287963046236763679840464906336460820092771576608949179490369560959172023803762121604537367480484454904813020571465575742167621771758297285588855780348124532628504375656267081524502076034450462453363957711423588564462359410967926129108254423738403169442962275313525090211150193152351753655320647462240059975524421967593395775474556909282436434768819792715421583046680529614081456106525995079634683099418509035139178267219932185253244635431462290992591538746689988757498385171283396181200109164354671626081737459054748676909257343535143447845914178339935485987786968424023853665499904458871096528510206968688488554809003023302634934661995576384412984644186040584904620134000331905339769671133648655782066212730857176672035329284056747345917084944700530653194430502696091705976574066958778759621388225888548018846210163747019389980467612464592848597117248618695639829210276569429620795957818158689306812335402128430790675507463182721856549198214754989116154033533659598310552791290593882800988094702448992894438801808070307049851850195267989691130483421110802879839277281985323874241668806764859225125410161803132306235945509452724402664282015328117123610009898983664646040344412148439748875511366459409227928226655799221851754434885674148486582518655637878205448377951277968732829875601637289704005258417834787847555648483819757359335789498323477968006653253642075967192018158060615413447524554116788891801582755182791156670714173012487803497754979736256055276809697876269405745078990359671824842557889850621222947751607946274060795438648599347917652671137920384914890476689089020665918436326492744007539167248829401443587333471435766378509883316985180911390828045034472612356238423369823751490637151629629084171459536151406052483342515069864981892600158973342676957874342712338983617062702048870400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

 

import java.math.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        input.nextLine();
        for(int i=0; i<T; i++){
            String numberString = input.nextLine();
            BigInteger bigNumber = new BigInteger(numberString);
            System.out.println(factorial(bigNumber));
        }
	}
 
	public static BigInteger factorial(BigInteger b){
    if(b.equals(BigInteger.ONE))
        return BigInteger.ONE;
    return b.multiply(factorial(b.subtract(BigInteger.ONE)));
}
}

 

 

18.B - Fibonacci numbers

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

(피보나치 숫자들) 반복문을 이용하여 18.2에 나열된 메소드를 다시 작성하시오. 즉, 반복문을 이용하여 피보나치 수열을 구하시오.

(Fibonacci numbers) Rewrite the fib method in Listing 18.2 using iterations.

 

INPUT

* Line 1 :  테스트 케이스 T (1~1,000)

* Line 2 ~ T+1 : n (1~20)

 

OUTPUT

* Line 1 ~ T : fib(n) 

 

SAMPLE INPUT

3 2 9 18

 

SAMPLE OUTPUT

1 34 2584

 

HINT

힌트 : 재귀호출 없이 fib(n)를 계산하려면, fib(n-2)와 fib(n-1)을 먼저 계산하여야 한다. f0과 f1을 전전항과 전항의 피보나치 숫자라고 하자. 구하고자 하는 피보나치 숫자는 f0 + f1이 될 것이다. 알고리즘은 다음과 같이 표현될 수 있다:

Hint: To compute fib(n) without recursion, you need to obtain fib(n - 2) and fib(n - 1) first. Let f0 and f1 denote the two previous Fibonacci numbers. The current Fibonacci number would then be f0 + f1. The algorithm can be described as follows:

f0 = 0; // For fib(0)
f1 = 1; // For fib(1)
for (int i = 1; i <= n; i++) {
	currentFib = f0 + f1;
	f0 = f1;
	f1 = currentFib;
}
// After the loop, currentFib is fib(n)

사용자 입력을 받아 피보나치 숫자를 출력하는 프로그램을 작성하시오.

Write a test program that prompts the user to enter an index and displays its

Fibonacci number.

 

import java.math.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        input.nextLine();
        for(int i=0; i<T; i++){
            int n = input.nextInt();
            BigInteger f0 = BigInteger.ZERO;
            BigInteger f1 = BigInteger.ONE;
            BigInteger fn = BigInteger.ZERO;
            for(int j = 0; j < n - 1; j++){
                fn = f0.add(f1);
                f0 = f1;
                f1 = fn;
            }
            if(n == 1)
                fn = BigInteger.ONE;
            System.out.println(fn);
        }
    }
}

 

 

Wrong Answer0
import java.math.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int T = input.nextInt();
        input.nextLine();
        for(int i=0; i<T; i++){
            int n = input.nextInt();
            BigInteger f0 = BigInteger.ZERO;
            BigInteger f1 = BigInteger.ONE;
            BigInteger fn = BigInteger.ZERO;
            for(int j = 0; j < n - 1; j++){
                fn = f0.add(f1);
                f0 = f1;
                f1 = fn;
            }
            System.out.println(fn);
        }
    }
}
반응형

 

 

18.C - Tower of Hanoi

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

(하노이의 탑) 18.8의 TowerOfHanoi.java를 수정하여, n개 원판들이 A탑에서 B탑으로 이동하는 횟수를 구하시오.

(힌트 : 정적 변수를 사용하여, 함수가 호출될 때마다 증가시키시오.)

(힌트2 : 하노이의 탑 원본은 3개의 탑에 대한 문제입니다.)

(Tower of Hanoi) Modify Listing 18.8, TowerOfHanoi.java, so that the program finds the number of moves needed to move n disks from tower A to tower B.

(Hint: Use a static variable and increment it every time the method is called.)

(Hint2 : Original Tower of Hanoi problem is question about 3 tower)

 

INPUT

* Line 1 :  테스트 케이스 T (1~1,000)

* Line 2 ~ T+1 : n (1~20)

 

OUTPUT

* Line 1 ~ T : n개 원판들의 이동 횟수

 

SAMPLE INPUT

3 9 20 7

 

SAMPLE OUTPUT

117 116515 31

 

import java.util.*;
public class Main {
    static int c = 0;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        for(int i = 0; i < n; i++){
            int m = input.nextInt();
            move(m, 'A', 'B', 'C');
            System.out.println(c);
            c = 0;
        }
    }
    public static void move(int n, char fT, char tT, char aT) {
        if(fT == 'A' && tT == 'B') c++;
        if (n == 1)
            return;
        else {
            move(n - 1, fT, aT, tT);
            move(n - 1, aT, tT, fT);
        }
    }
}

 

 

18.D - 문자열 순열

Time Limit: 1s Memory Limit: 128MB

 

DESCRIPTION

(String permutation) Write a recursive method to print all the permutations of a string. For example, for the string abc, the permuation is

 

입력된 문자열의 모든 순서를 출력하는 프로그램을 recursive method 로 작성하시오.

예를들어, abc 문자열이 입력되면

abc, acb, bac, bca, cab, cba

을 출력해야한다.

 

INPUT

Line 1 : 랜덤한 길이의 문자열

 

OUTPUT

Line 1 ~ 길이! : 각 문자열 순열

SAMPLE INPUTABCD SAMPLE OUTPUTABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

 

import java.util.*;
public class Main {
    static int c = 0;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        int n = 1;
        for(int i = 1; i <= s.length(); i++)
            n *= i;
        String ans[] = new String[n];
        print(ans, s, 0, s.length() - 1);
        Arrays.sort(ans);
        for(int i = 0; i < ans.length; i++)
            System.out.println(ans[i]);
    }
    public static void print(String ans[], String s, int f, int l){
        if(f == l)
            ans[c++] = s;
        else{
            for(int i = f; i <= l; i++){
                s = swap(s, f, i);
                print(ans, s, f + 1, l);
                s = swap(s, f, i);
            }
        }
    }
    public static String swap(String s, int i, int j) {
        char temp = s.charAt(i);
        s = s.substring(0, i) + s.charAt(j) + s.substring(i + 1, s.length());
        s = s.substring(0, j) + temp + s.substring(j + 1, s.length());
        return s;
    }
}

 

Wrong Answer0
import java.util.*;
public class Main {
    static int c = 0;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        print(s, 0, s.length() - 1);
    }
    public static void print(String s, int f, int l){
        if(f == l)
            System.out.println(s);
        else{
            for(int i = f; i <= l; i++){
                s = swap(s, f, i);
                print(s, f + 1, l);
                s = swap(s, f, i);
            }
        }
    }
    public static String swap(String s, int i, int j) {
        char temp = s.charAt(i);
        s = s.substring(0, i) + s.charAt(j) + s.substring(i + 1, s.length());
        s = s.substring(0, j) + temp + s.substring(j + 1, s.length());
        return s;
    }
}
반응형

댓글