작도닷넷 블로그
작도닷넷 블로그

컴퓨터 - ACM ICPC

100. The 3n + 1 problem (Solution)

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

http://xacdo.net/tt/rserver.php?mode=tb&sl=1452

이름
비밀번호
홈페이지 (없어도 됩니다)

비밀글로 등록
작도닷넷은 당신을 사랑합니다.

[이전 목록]   [1] ... [2][3][4][5][6][7][8]   [다음 목록]

최근 글

이웃로그 관리자 옛날 작도닷넷 태터툴즈 ©현경우(xacdo) since 2001