컴퓨터 - ACM ICPC
08/11/20 06:49(년/월/일 시:분)
http://acm.uva.es/p/v1/100.html
The 3n + 1 problem
맨 첫번째 문제로 무척 유명하다.
원래 C++로 짜면 그냥 풀어도 시간 초과가 안 되는데, Java는 느려서 약간 방법을 써야 한다.
http://acm.uva.es/problemset/data/p100.java.html
100 Java "Easy algorithm"
...심지어는 예제로 올려놓은 것도 느려서 안 된다.
http://blog.naver.com/gods_gamer/30024362178
3n+1 문제 (The 3n+1 Problem / 알고리즘 트레이닝 북 1번 문제)
...풀었던 숫자는 다시 안 풀고 넘어가는 방법을 베꼈다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanKeyboard = new Scanner(System.in);
while(scanKeyboard.hasNextInt())
{
int firstInput = scanKeyboard.nextInt();
int secondInput = scanKeyboard.nextInt();
int minNum, maxNum;
if( firstInput < secondInput )
{
minNum = firstInput;
maxNum = secondInput;
}
else
{
maxNum = firstInput;
minNum = secondInput;
}
boolean cyclesDone[] = new boolean[maxNum+1]; //default: false
int cycleMax = 0;
for(int currNum=maxNum; currNum>=minNum; currNum--)
{
if(cyclesDone[currNum] == false) //check it's not done
{
int cycle = 1;
for(int n=currNum; n>1; cycle++)
{
if( (n%2) == 1 ) //if odd number
{
n = 3*n + 1;
}
else //if even number
{
n >>= 1; // n=n/2;
}
if( (n>=minNum)&& (n<=maxNum) )
{
cyclesDone[n] = true; //check it's done
}
}
if( cycle > cycleMax)
{
cycleMax = cycle;
}
}
else
{
}
}
System.out.println(firstInput + " " + secondInput + " " + cycleMax);
}
}
}
Accepted JAVA 2.900 2008-11-20 06:45:29
시간제한이 3초인데 2.9초로 통과;;;
참고로 output이 처음에는 헷갈렸다.
firstInput과 secondInput을 크기 순으로 단순히 swap하면, 나중에 출력할때도 순서가 바뀐다.
그러니까 output에 minNum, maxNum을 출력하면 안되고 firstInput, secondInput을 출력해야 함.
input: 10 1
output: 1 10 20 (X)
output: 10 1 20 (O)
http://icpcres.ecs.baylor.edu/onlinejudge
UVa Online Judge