12886번 - 돌 그룹
문제
오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.
강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.
크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)
출력
돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.
예제 입력 1
10 15 35
예제 출력 1
1
예제 입력 2
1 1 2
예제 출력 2
0
풀이
1. 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다
2. 크기가 같지 않은 두 그룹을 고른다.
3. 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다
4. X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
목표: 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.
여기서 파악해야할 점은
X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
이부분이다.
결국 Y에서 X개를 X에다가 넘겨주기때문에 ABC의 합은 변하지 않는다.
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static int sum = 0;
public static boolean[][] check = new boolean[1501][1501];
public static void go(int x, int y) {
if (check[x][y]) return;
check[x][y] = true;
int[] a = {x, y, sum-x-y};
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
if (a[i] < a[j]) {
int[] b = {x, y, sum-x-y};
b[i] += a[i];
b[j] -= a[i];
go(b[0], b[1]);
}
}
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
sum = x + y + z;
if (sum % 3 != 0) { //3개의 그룹에 같은 값으로 나눠야하는데 똑같이 나눌려면 3으로 나눠떨어져야한ㄷ다.
System.out.println(0);
System.exit(0);
}
//sum에서 구한 두개를 빼면 나머지 숫자는 자련스럽게 알게되기때문에 2개의 정점만 필요
go(x, y);
//똑같이 나눴을 경우 배열에 가서 방문했는지만 알면됨
if (check[sum/3][sum/3]) {
System.out.println(1);
} else {
System.out.println(0);
}
}
}
Author And Source
이 문제에 관하여(12886번 - 돌 그룹), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yuiopre98/12886번-돌-그룹저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)