오늘 푼 문제는 백준 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풀이 방법
기본적인 접근 방법은 주어진 input에서 두 개를 고르는 조합을 모두 구한 후, 두 개 중에서 작은 값과 큰 값을 구하여 문제에 주어진 규칙에 따라 연산을 진행하여 새로운 세 개의 숫자를 만들어낸다. 이 과정을 반복하면서 세 숫자가 모두 같은 경우가 나온다면 종료하면 된다.
이제 이 방법을 코드적으로 어떻게 구현하였는지와 주의할 점 ? 이슈 ? 등을 이야기해보려 한다.
우선 조합을 구하는 것은 나는 재귀를 통해서 구하였으나, 숫자가 3개로 정해져있기에 3개밖에 안 나오는 것이 고정이라서 그냥 직접 분기로 작성하는 것이 시간적으로는 더 적게 걸리지 않을까 싶다. 나는 분기문에 같은 코드를 넣는 것이 싫어서 그냥 재귀로 작성해서 그 안에서 연산까지 처리해주었다.
기본적으로 반복하면서 탐색을 진행해야 하는데 나는 BFS 방식으로 해주었다. 즉, 탐색의 대상이되는 세개의 숫자를 배열에 담아서 큐에 넣어주었다. 그래서 큐에서 하나씩 꺼내서 조합을 구하고 연산을하여 새로운 세 개의 숫자를 구하고 이를 다시 큐에 넣어주는 과정으로 탐색을 진행하였다. 그리고 큐에서 하나씩 꺼내서 탐색을 하기 전에 종료 조건인 세 숫자가 같은지를 확인하고 같다면 탐색을 멈추어야 한다.
이 때 BFS 탐색에서 비효율성과 무한 루프를 피하기 위해서 이미 탐색을 진행한 숫자 조합은 다시 큐에 넣어주지 말아야한다. 그를 위해서 visited를 체크해주는데, 이 세 개의 숫자 조합을 어떻게 유니크하게 또 효율적으로 다룰 수 있을지 고민이 되었다. 이것은 내 머리에서 나온 방법이 과연 효과적일까를 의심하여 서치를 좀 하였다..ㅎㅎ..
그래서 얻은 힌트는 연산 규칙을 보면 min*=2 / max-=min 이므로 min만큼 늘이고 줄이는 것이기에 합은 계속 동일하다는 것이다. 그러므로 두 개의 숫자만 알아도 나머지 하나는 알 수 있는 것이다. 그래서 visited를 이차원 배열로 해주었다.
이제 여기서 힌트를 얻은 다른 포스팅을 보면 그냥 두 개의 값을 넣어주더라..! 근데 그러면 불필요한 중복 탐색이 조금 더 생길 거 같았다. 왜냐면 조합은 순서가 없으므로 ABC ACB 가 같은데 visited[A][B] visited[A][C]는 다르기 때문이다. 그래서 나는 visited 체크는 모두 정렬 후 진행해주었다. ( 근데 이건 과연 매번 정렬하는게 더 좋을까 모르겠다 나는 원소가 3개로 고정이기에,, 하지만 같은 조합을 다르게 visited 체크해줘서 생길수 있는 중복은 더 클 거 같아서,, 얕은 고민으로 그냥 정렬을 택햇다 ㅋㅋ + 확실하게 방문한 노드는 안 방문하게 하고 싶어서 )
추가로 내 코드에서 개선할 부분이 생각났는데, 내일 출근을 위해 얼른 자야해서 넘어간 부분을 짚어보자면 첫째로, 조합으로 고른 두 숫자가 같은 경우를 제외해주면 좋을 듯 싶다. 둘째로, 세 숫자가 같은지를 큐에서 꺼낼때 체크하는데 사실 넣을때 체크해서 종료해주면 더 좋을텐데 이건 흐름을 좀 고민해서 개선해야해서 패스했다 ~
+) 아 그리고 dp배열 사이즈를 얼마나 할당해야할지 고민이 됐다.. 머리가 안돌아가.. 내 생각에는 1000만 해도 될 거 같은데 아니라는 글을 보았다. 테스트 해보려 했는데 까먹었다 이건 꼭 다시 해볼 것이다 !
끄읕.
코드
import java.io.*;
import java.util.*;
public class Main {
private static Queue<int[]> queue = new LinkedList<>();
private static boolean[][] genVisited = new boolean[1500][1500];
public static void combination(int[] input, int start, int depth, int r, int[] output, boolean[] visited){
if(depth == r){
int min = Math.min(output[0], output[1]);
int max = Math.max(output[0], output[1]);
int other = 0;
for(int i=0; i< visited.length; i++){
if(!visited[i]) other = input[i];
}
max = max-min;
min = min*2;
int[] temp = {min, max, other};
Arrays.sort(temp);
if(!genVisited[temp[0]][temp[1]]){
queue.add(temp);
genVisited[temp[0]][temp[1]] = true;
}
return;
}
for(int i=start; i<input.length; i++){
if(!visited[i]){
visited[i] = true;
output[depth] = input[i];
combination(input, i+1, depth+1, r, output, visited);
visited[i] = false;
}
}
}
public static boolean isAllSame(int[] elem){
for(int i=1; i< elem.length; i++){
if(elem[i-1] != elem[i]) return false;
}
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int[] input = new int[3];
int sum = 0;
for(int i=0; i<3; i++){
input[i] = Integer.parseInt(st.nextToken());
sum += input[i];
}
boolean flag = false;
if(sum%3 == 0) {
Arrays.sort(input);
queue.add(input);
genVisited[input[0]][input[1]] = true;
int[] cur;
while(!queue.isEmpty()){
cur = queue.poll();
if(isAllSame(cur)){
flag = true;
break;
}
combination(cur, 0, 0, 2, new int[2], new boolean[3]);
}
}
if(flag) bw.write(1+"\n");
else bw.write(0+"\n");
bw.flush();
bw.close();
br.close();
}
}