AOJ1295 Cubist Artwork

問題リンク Cubist Artwork

• 概要

1*1*1の立方体を積んでアートを作る。作ろうとするアートを正面から見たシルエットと側面から見たシルエットが与えられる。このシルエットの形になるようなアートを作るために必要な立方体の最小個数を答えよ。
正面から見たシルエットの列数, 側面から見たシルエットの列数 <= 10
1 <= 各列のシルエットの高さ <= 10

• 解法

まず、正面から見たシルエットの数だけは絶対に必要なので数えます。
側面から見たシルエットは、正面から見えるシルエットのどれかと高さが一致したらそれが使えるので、別途加算する必要がありません。正面のもの全てと高さが違ったり、その高さを別の側面のシルエットを表現するために使ってしまっていたら、側面の高さの分だけ立方体が必要になるので加算します。

• ソース

import java.util.Scanner;

//Cubist Artwork
public class AOJ1295 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), d = sc.nextInt();
			if((n|d)==0)break;
			int[] h = new int[21];
			int res = 0;
			while(n--!=0){
				int x = sc.nextInt();
				res+=x; h[x]++;
			}
			while(d--!=0){
				int x = sc.nextInt();
				if(h[x]>0)h[x]--;
				else res+=x;
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1295().run();
	}
}