[Java] 백준 1679번 : 숫자놀이

문제

홀순이(holsoon)와 짝순이(jjaksoon) 둘이서 숫자 게임을 한다. 예를 들어, 정수 1과 3이 주어지고, 이 둘을 통틀어 5번까지 마음대로 사용하여 그 합을 구하여 1,2,3,…을 만드는 놀이다. 이 경우 먼저 홀순이가 1 하나만을 사용하여 1을 만든다. 짝순이는 1+1로 1을 두 번 사용하여 2를 만들고, 다시 홀순이는 3을 만들어야하는데 1+1+1로 1을 세 번 사용하거나 3을 한 번 사용하여 3을 만든다. 짝순이는 1+1+1+1, 1+3으로 4를 만든다. 서로 번갈아서 상대방의 수보다 1이 큰 수를 만들어야 한다. 단, 1과 3을 통틀어 최대 5번 사용한다. 이런 식으로 진행하면 13까지는 만들 수 있지만 14를 만들지 못하게 되므로 짝순이가 졌다. 

숫자 게임에서 사용하는 정수 N개와 최대 사용 횟수 K가 주어질 때, 누가 어느 수에서 이기는지를 판별하는 프로그램을 작성해보자. 사용하는 정수에는 반드시 1이 포함된다. 그렇지 않으면 홀순이가 1을 만들지 못하므로 무조건 지게 된다. 1이 꼭 있으니 상대방이 만든 방법에 1만 한 번 더 쓰면 된다고 생각하기 쉽지만, 최대 사용 횟수가 정해져 있으므로, 이 방법이 수가 커지는 경우에는 잘 되지 않는다. 위에서 13을 홀순이가 만들었지만 짝순이는 최대 사용 횟수 때문에 14를 만들지 못하고 진다.

입력

첫째 줄에 숫자 게임에서 사용하는 정수의 수 N이, 둘째 줄에는 사용하는 정수가 크기 순으로 주어진다. 셋째 줄에는 최대 사용 횟수 K가 주어진다.

출력

첫째 줄에 누가 몇 번째 수에서 이겼는지를 출력한다. 예제에서는 짝순이가 14를 못 만들어서, 홀순이가 14에서 이겼다.

제한

• 1 ≤ N ≤ 1,000
• 1 ≤ K ≤ 50
• 숫자 게임에서 사용하는 정수는 1000보다 작거나 같은 자연수이고, 중복되는 수가 주어지지 않는다.

예제 입력 1

2
1 3
5

예제 출력 1

holsoon win at 14

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int N, K, next;
	private static int[] nums;
	private static boolean[] visited;

	static class Number {
		int val, cnt;

		public Number(int val, int cnt) {
			super();
			this.val = val;
			this.cnt = cnt;
		}

		@Override
		public String toString() {
			return "Number [val=" + val + ", cnt=" + cnt + "]";
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		nums = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			nums[i] = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(br.readLine());
		visited=new boolean[nums[N-1]*K+2];	// (가능한 최대 수+1)까지 체크

		bfs();
		for(int i=1;i<visited.length;i++) {
			if(!visited[i]) {
				if(i%2==0) System.out.println("holsoon win at "+i);
				else System.out.println("jjaksoon win at "+i);
				break;
			}
		}
	}

	private static void bfs() {	// 숫자 개수가 K개 이하일 때 가능한 모든 경우의 수를 bfs로 구함
		Queue<Number> queue=new LinkedList<>();
		queue.add(new Number(0,0));
		
		while(!queue.isEmpty()) {
			Number q=queue.poll();
			
			if(q.cnt==K) continue;	// K개를 다 쓴 경우는 패스
			for(int i=0;i<N;i++) {
				int now=q.val+nums[i];	// 현재 숫자에 숫자 하나를 더함
				if(!visited[now]) {	// 아직 방문하지 않은 숫자인 경우, 방문 처리 후 큐에 넣어줌
					visited[now]=true;
					queue.add(new Number(now, q.cnt+1));
				}
			}
		}
	}
}

bfs + dp를 이용하여 해결해준 문제입니다. bfs를 이용할 생각도, dp를 리스트도 이용할 생각도 하기 힘들어서 고민하게 되었던 문제였습니다.

 

1. (가장 큰 수 x 최대 사용 횟수) 까지 전부 가능한 경우 그 다음 숫자가 만들 수 없는 수가 되므로,

visited 배열을 (가장 큰 수 x 최대 사용 횟수 + 1) 로 크기 설정을 해주었습니다.

2. Number 클래스를 만들어 현재 만들어진 수와 해당 수를 만들기위해 사용된 숫자의 개수를 멤버 변수로 저장해줍니다.

3. bfs를 통해 큐에 Number를 대입하고 빼며 가능한 K개 이하의 모든 경우를 구해줍니다.