학교에서 무료함을 달래기 위해 acm programming contest 기출문제를 풀어보는데, ToyProblems 에서도 다룰만한 쉬운 문제가 있기에 이렇게 소개합니다. [http://acm.uva.es/p/v1/100.html 원문보기] ---- === 이 문제는 === 인기도:A(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:1(1~4) CS에서 등장하는 문제의 종류는 여러가지가 있는데 (예를 들어, NP, Unsolvable, Recursive...) 이 문제는 '입력에 대해 출력이 어떻게 나올지 모르는' 이라고 분류할만한 것에 대한 분석을 하는 것이다. (해석이 애매하군요; ) 다음과 같은 알고리즘이 있다 {{{ 1. input n 2. print n 3. if n == 1 then STOP 4. if n is odd then n = 3n + 1 5. else n = n/2 6. GOTO 2 }}} 만약 입력으로 22가 주어졌을때 출력값은 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 가 될 것이다. 이 알고리즘은 간단해 보이지만 n의 값이 1로 되어 알고리즘이 종료될지는 모르는 일이다. 하지만 이는 0과 1000000 사이의 숫자, 아니 이보다 더 큰 숫자에 대해서도 n의 값이 1이 된다고 증명되었다. 입력으로 22가 주어졌을때, 출력되는 값의 수 n(22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1) 는 22 16이다. 이를 n에 대한 cycle-length 라고 한다. 정수 i와 j 에 대해 두 수 사이에 존재하는 cycle-length 값들중의 최대값을 구할 것이다. 입력은 아래와 같이 한 줄에 한 쌍의 정수로 이루어져 있다. 출력값은 이 두 정수 사이의 cycle-length 중에서 최대값을 구하는 것이다. === 입력 === {{{ 1 10 100 200 201 210 900 1000 }}} === 출력 === {{{ 1 10 20 100 200 125 201 210 89 900 1000 174 }}} === 풀이 === || 작성자 || 사용언어 || 개발시간 || 코드 || 실행시간(i=1,j=999999 기준 4초 통과) || || [강희경] || Python || 1시간 || [3N+1Problem/강희경] || X || || [황재선] || Python || ? || [3N+1Problem/황재선] || . || || [김회영] || C++ || ? || [3N+1Problem/김회영] || . || || [문보창] || C++ || ? || [3N+1Problem/문보창] || X || || [구자겸] || C || ? || [3N+1Problem/구자겸] || . || || [신재동] || C++ || 10분 || [3N+1Problem/신재동] || . || || [Leonardong] || Python || 46분 || [3N+1Problem/Leonardong] || . || || [곽세환] || C++ || ? || [3N+1Problem/곽세환] || . || || [1002] || Python || 13분 || [3N+1Problem/1002] ||. || || [1002] || Python || 30분 || [3N+1Problem/1002_2] || No-Psyco : 9.25초, With-Psyco : 3.8초 || || [허아영] || C++ || 1시간 20분 || [3N 1Problem/허아영] || .|| || [이도현] || C++ || 1시간 || [3n+1/이도현]|| . || || [임인택] || [HaskellLanguage] || 30분 || [http://janbyul.com/moin/moin.cgi/HaskellLanguage/3N%2B1Problem 여기] || . || || [김상섭] || C++ || 엄청..ㅡㅜ || [3N+1/김상섭] || . || See also BioinfoWiki:AlgorithmQuiz/3Plus1 === 문제 2탄 === * 기존의 코드를 수정해서 가장 큰 Cycle Length 가 아닌 3번째로 큰 Cycle Length 를 구해보세요. || 작성자 || 사용언어 || 개발(수정)시간 || 코드 || || [1002] || Python || 16분(3분) || . || === 쓰레드 === 실행시간(i=1,j=1000000 기준 4초 통과)는 파이썬의 경우 가능할런지 모르겠네요. 나름대로 알고리즘을 보강했는데도 1, 100000에 빌빌 거리니...--[강희경] ---- [문제분류]