U E D R , A S I H C RSS

Hanoi Tower Troubles Again!/황재선

2006.1.15

느낌

  • 문제 이해를 잘못했다-_-; 한 기둥에 놓여진 전체 번호의 합이 완전제곱수인지 체크했었다.ㅡㅜ
  • 초기에 잘못 접근했다 쳐도 구현 시간이 오래 걸렸다.

소스 코드

~java
import static java.lang.Math.ceil;
import static java.lang.Math.floor;
import static java.lang.Math.sqrt;

import java.util.Scanner;

public class HanoiTower {
	
	public int readNumber() {
		return new Scanner(System.in).nextInt();
	}
	
	public boolean canBallPut(int[] prev, int peg, int ballNumber) {
		if (prev[peg] == 0) {
			return true;
		}
		double squareNumber = sqrt(prev[peg] + ballNumber);
		return ceil(squareNumber) == floor(squareNumber);
	}
	
	public int maxBall(int numOfPeg) {
		int[] prevNumber = new int[numOfPeg + 1];
		
		int ballNumber = 1;
		int oldBallNumber = 0;
		while(oldBallNumber != ballNumber) {
			oldBallNumber = ballNumber;
			for(int peg = 1; peg <= numOfPeg; peg++) {
				if (canBallPut(prevNumber, peg, ballNumber)) {
					prevNumber[peg] = ballNumber++;
					break;
				}
			}
			if (ballNumber == Integer.MAX_VALUE) {
				return -1;
			}
		}
		return ballNumber - 1;
	}
	
	public void printNumberOfBall(int numOfBall) {
		System.out.println(numOfBall);
	}

	public static void main(String[] args) {
		HanoiTower hanoi = new HanoiTower();
		
		int testCase = hanoi.readNumber();
		for(int i = 0; i < testCase; i++) {
			int numOfPeg = hanoi.readNumber();
			int numOfBall = hanoi.maxBall(numOfPeg);
			hanoi.printNumberOfBall(numOfBall);
		}
	}
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0982 sec