5회차 - 알고리즘 기록 : 세 카드

문제3I-세 카드

본 문제는 앞 문제를 조금 변형하면 해결 할 수 있는 숙제 입니다.

선택해야 할 카드가 세 장일 때에도 앞의 문제와 같은 방법을 적용할 수 있을까 고민해보세요.

힌트> 문제의 입력 사이즈가 작아졌다!

실습 내용

 지수가 살고 있는 이상한 나라에서는 독특한 복권제도가 존재한다. 이상한 나라에서는 매 주 당첨 될 자연수 번호를 정해두며, 복권을 구매한 사람은 그 자리에서 수 많은 카드들 중 하나를 뽑을 수 있는 기회가 세 번 주어진다. 즉, 똑같은 카드를 세 번 뽑을 수 도 있다. 이렇게 세 번에 걸쳐 뽑은 카드들에 적혀있는 세 자연수를 더하여 당첨 번호로 지정된 자연수와 일치한다면 그 사람은 당첨되는 것이다.

 복권 담당자인 미주는 이번 주에 복권에 사용 될 당첨 번호들을 정하려고 한다. 하지만 매 번 실제로 그 당첨번호가 세 카드에 적힌 숫자들의 합으로 만들어 질 수 있는지 (즉, 실제로 당첨될 수 있는 번호인지) 검사하는 과정이 너무 번거로워 고민을 하고 있다. 미주를 도와서 주어진 카드를 조합해 당첨 번호들을 만들 수 있는지 판단하는 프로그램을 작성해주자.

 

 

입력 형식

 첫 줄에는 사용할 카드의 수 N과 당첨 번호의 숫자 M이 공백으로 구분되어 주어진다. N은 1이상 1,000이하의 자연수이며 M은 1이상 100이하의 자연수이다.

두 번째 줄에는 N개의 카드에 적힌 숫자들이 공백으로 구분되어 1이상 1억 이하의 자연수로 주어진다. 

세 번째 줄에는 M개의 이번 주에 사용 될 당첨번호들이 공백으로 구분되어 주어진다. 당첨번호들은 모두 서로다른 1이상 3억 이하의 자연수이다. 

 

출력 형식

 M개의 당첨번호 들 중 실제로 세 카드에 적힌 숫자의 합으로 표현될 수 있는 당첨번호들을 모두 출력한다.

• 실제로 만들 수 있는 당첨번호가 여러개라면, 오름차순으로 정렬하고 각 숫자는 공백으로 구분하여 한 줄에 출력한다.
• 실제로 만들 수 있는 당첨번호가 존재하지 않는다면 NO를 출력한다.

 

결과 코드

package 알고리즘;
import java.io.*;
import java.lang.*;
import java.util.*;


public class 세카드 {
	public static final Scanner scanner = new Scanner(System.in);

	/**
	 * 중복을 포함해 세 카드의 합으로 만들 수 있는 당첨번호들의 리스트를 반환하는 함수
	 * @param n     카드의 수
	 * @param m     검사하려는 당첨번호의 수
	 * @param cards   각 카드에 적힌 숫자들
	 * @param target  검사하려는 각 당첨번호 리스트
	 * @return      세 카드의 합으로 표현될 수 있는 당첨번호들의 오름차순 리스트
	 */
	public static ArrayList<Integer> getPossibleTargets(int n, int m, int[] cards, int[] target)
	{
		ArrayList<Integer> possibleTargets = new ArrayList<>(); //만들 수 있는 당첨번호들

		Arrays.sort(cards);
		
		for(int k : target)
		{ //검사 할 모든 당첨 번호 k에 대하여

			boolean possible = false; // k를 세 숫자의 합으로 표현할 수 있는지 여부
			for(int i = 0 ; i < n ; i+= 1)
			{   // 카드 중 하나 x를 선택한다.
				int x = cards[i];
				for(int j = 0 ; j <= i ; j += 1)
				{   // 카드 중 하나 y를 선택한다
					int y = cards[j];
					int z = k - (x + y); // k = (x +  y )+ z 가 되는 z를 계산한다
					
					// z가 cards[]에 존재한다면?
					if( Arrays.binarySearch(cards, z) >= 0 ) {
						// k = x + y + z 가 가능한 <x, y, z>가 존재한다.
						possible = true;
						break;
					}
				}
				if(possible)
				{   // 이미 찾았다면 탈출한다
					break;
				}
			}
			if(possible)
			{	// 세 카드의 합으로 k를 만들 수 있다면, 추가한다.
				possibleTargets.add(k);
			}
		}

		Collections.sort(possibleTargets);
		return possibleTargets;
	}

	public static void main(String[] args) throws Exception {
		int n = scanner.nextInt();  // 카드의 수
		int m = scanner.nextInt();  // 검사 할 후보 당첨번호의 수

		int[] cards = new int[n];
		int[] targets = new int[m];

		// 각 카드 정보를 입력받는다
		for(int i = 0 ; i < n ; i ++)
		{
			cards[i] = scanner.nextInt();
		}

		// 각 당첨번호를 입력받는다
		for(int i = 0 ; i < m ; i ++)
		{
			targets[i] = scanner.nextInt();
		}

		ArrayList<Integer> answers = getPossibleTargets(n, m, cards, targets);

		if(answers.size() == 0)
		{
			System.out.print("NO");
		}else{
			for(int i = 0 ; i < answers.size() ; i++)
			{
				if( i > 0 )
				{
					System.out.print(" ");
				}
				System.out.print(answers.get(i));
			}
		}
	}
}