Apr 072012
 

미로 최단거리 문제 – 프로그래밍 콘테스트 챌린징 책 P50 문제

 

너비 우선 탐색을 통해 문제를 풀음.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Save
{
	public int x;
	public int y;
	public int num;

	public Save(int x, int y, int num
	{
		this.x = x;
		this.y = y;
		this.num = num;
	}
}

public class Miro {

	public static void main(String[] args) {
		int x, y;
		int num = 0;
		int start_x = 0;
		int start_y = 0;
		int[][] arr = new int[102][102];
		Queue<Save> queue = new LinkedList<Save>();
		Scanner scan = new Scanner(System.in);

		x = scan.nextInt();
		y = scan.nextInt();

		for (int i = 0; i <= x + 1; i++) {
			for (int j = 0; j <= y + 1; j++)
			{
				arr[i][j] = -100;
			}
		}

		for (int i = 1; i <= x; i++)
		{
			char[] tmp = scan.next().toCharArray();

			for (int j = 0; j < y; j++)
			{
				if (tmp[j] == 'S')
				{
					start_x = i;
					start_y = j + 1;
				}
				else if (tmp[j] == '.')
				{
					arr[i][j + 1] = 0;
				}
				else if (tmp[j] == 'G')
				{
					arr[i][j + 1] = Integer.MAX_VALUE;
				}
			}
		}

		queue.add(new Save(start_x, start_y, num));

		while (!queue.isEmpty())
		{
			Save now = queue.poll();
			num = ++now.num;

			if (arr[now.x][now.y] == Integer.MAX_VALUE)
			{
				break;
			}

			arr[now.x][now.y] = now.num;

			if (arr[now.x - 1][now.y] == 0)
			{
				queue.add(new Save(now.x - 1, now.y, now.num));
			}
			if (arr[now.x][now.y - 1] == 0)
			{
				queue.add(new Save(now.x, now.y - 1, now.num));
			}
			if (arr[now.x + 1][now.y] == 0)
			{
				queue.add(new Save(now.x + 1, now.y, now.num));
			}
			if (arr[now.x][now.y + 1] == 0)
			{
				queue.add(new Save(now.x, now.y + 1, now.num));
			}
		}
		System.out.println(num);
	}
}

 

Apr 072012
 

 

Lake Counting (POJ No.2386)

 

재귀 함수를 이용하여 구현하였다.

import java.util.Scanner;

public class P2386 {

	public static int[][] arr = new int[102][102];

	public static void check(int x, int y, int num) {

		arr[x][y] = num;

		if (arr[x - 1][y] == 0)
			check(x - 1, y, num);

		if (arr[x + 1][y] == 0)
			check(x + 1, y, num);

		if (arr[x - 1][y - 1] == 0)
			check(x - 1, y - 1, num);

		if (arr[x][y - 1] == 0)
			check(x, y - 1, num);

		if (arr[x + 1][y - 1] == 0)
			check(x + 1, y - 1, num);

		if (arr[x - 1][y + 1] == 0)
			check(x - 1, y + 1, num);

		if (arr[x][y + 1] == 0)
			check(x, y + 1, num);

		if (arr[x + 1][y + 1] == 0)
			check(x + 1, y + 1, num);

	}

	public static void main(String[] args) {

		int x, y;
		int num = 0;
		Scanner scan = new Scanner(System.in);

		x = scan.nextInt();
		y = scan.nextInt();

		for (int i = 0; i <= x + 1; i++)
		{
			for (int j = 0; j <= y + 1; j++)
			{
				arr[i][j] = -1;
			}
		}

		for (int i = 1; i <= x; i++)
		{
			char[] tmp = scan.next().toCharArray();

			for (int j = 0; j < y; j++)
			{
				if (tmp[j] == 'W')
				{
					arr[i][j + 1] = 0;
				}
			}
		}

		for (int i = 1; i <= x; i++)
		{
			for (int j = 1; j <= y; j++)
			{
				if (arr[i][j] == 0)
				{
					check(i, j, ++num);
				}
			}
		}

		System.out.println(num);
	}
}

 

Apr 042012
 

개미가 부디칠 경우 통과한다고 보고 작성.,

 

속도는 O(n)

import java.util.Scanner;

public class P1852 {

	/**
	 * @param args
	 */

	public static void main(String[] args) {
		int testcase;
		Scanner scan = new Scanner(System.in);

		testcase = scan.nextInt();

		while (testcase– > 0)
		{
			int l = scan.nextInt();
			int n = scan.nextInt();

			int max = 0;
			int min = 0;

			for (int i=0; i<n; i++)
			{
				int t = scan.nextInt();

				max = Math.max(max, Math.max(l-t, t));
				min = Math.max(min, Math.min(l-t, t));
			}

			System.out.println(min + ” ” + max);
		}
	}
}

 

Sep 022011
 

처음에 C언어로 짰으나 1000을 입력해본 결과 Integer 범위를 넘어서는 것을 알 수 있었다. long long으로 바꿨는데도 실패.. 값이 매우 크다고 느낀 나는 Java의 BigInteger를 사용하여 구현하는 것으로 방향을 바꾸었다.

 이 문제의 점화식은 아래와 같다.
  f(1) = 2
  f(2) = 5
  f(3) = 13
  f(n) = 2 * f(n-1) + f(n-2) + f(n-3)

 

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

static BigInteger[] Data = new BigInteger[1002];

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

Data[1] = new BigInteger(“2”);

Data[2] = new BigInteger(“5”);

Data[3] = new BigInteger(“13”);

while (scan.hasNext())

{

int n = scan.nextInt();

if (n > 3)

{

for (int i = 4; i<=n; i++)

{

if (Data[i] != null)

continue;

Data[i] = Data[i-1].shiftLeft(1).add(Data[i-2]).add(Data[i-3]);

}

}

System.out.println(Data[n]);

}

}

}

 

Aug 312011
 

단순한 실수 때문에 몇번 실패 했다.. 출력할 때 개행에 주의해야할 것 같다.

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

public static void main(String[] args)

{

Scanner scan = new Scanner(System.in);

int testcase;

testcase = scan.nextInt();

while (testcase– > 0)

{

BigInteger n = scan.nextBigInteger();

int count = 0;

boolean sign = true;

while (sign)

{

String n1 = n.toString();

StringBuffer sb1 = new StringBuffer(n1);

String n2 = sb1.reverse().toString();

if (n1.equals(n2))

{

sign = false;

}

else

{

BigInteger p1 = new BigInteger(n1);

BigInteger p2 = new BigInteger(n2);

n = p1.add(p2);

count++;

}

}

System.out.println(count + ” ” + n);

}

}

}

Aug 172011
 

 # 문제점
   – 입력값의 반올림 주의 : Cent 이하 단위를 무시할 것.
   – 나머지 돈의 균등분배.

#include <iostream>

#include <algorithm>

#include <iomanip>

#include <cmath>

#include <functional> 

using namespace std;

int main()

{

int size;

int humens[1005];

int humens_spent[1005];

cin >> size;

while (size)

{

int sum = 0;

int avg;

for (int i=0; i<size; i++)

{

double temp;

cin >> temp;

humens[i] = (int)(temp * 100 + 0.5);

sum += humens[i];

}

sort(&humens[0], &humens[size], greater<int>() );

avg = sum/size;

int remain = sum% size;

sum = 0;

for (int i=0; i<size; i++)

{

humens_spent[i] = avg;

}

for (int i=0; i<remain; i++)

{

humens_spent[i]++;

}

for (int i=0; i<size; i++)

{

sum += abs(humens_spent[i] – humens[i]);

}

cout<< “$”<< fixed << setprecision(2) << (sum/2)/100.0 << endl;

cin >> size;

}

return 0;

}