結果

問題 No.4 おもりと天秤
ユーザー ShotaroSuzuShotaroSuzu
提出日時 2020-07-02 15:10:03
言語 Java19
(openjdk 21)
結果
AC  
実行時間 143 ms / 5,000 ms
コード長 2,574 bytes
コンパイル時間 3,390 ms
コンパイル使用メモリ 74,744 KB
実行使用メモリ 56,372 KB
最終ジャッジ日時 2023-10-13 03:19:50
合計ジャッジ時間 7,972 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 123 ms
55,980 KB
testcase_01 AC 124 ms
53,828 KB
testcase_02 AC 124 ms
55,736 KB
testcase_03 AC 123 ms
56,040 KB
testcase_04 AC 123 ms
55,704 KB
testcase_05 AC 143 ms
55,816 KB
testcase_06 AC 123 ms
55,708 KB
testcase_07 AC 141 ms
55,880 KB
testcase_08 AC 132 ms
55,724 KB
testcase_09 AC 141 ms
55,920 KB
testcase_10 AC 141 ms
55,780 KB
testcase_11 AC 121 ms
55,676 KB
testcase_12 AC 122 ms
55,940 KB
testcase_13 AC 120 ms
55,724 KB
testcase_14 AC 120 ms
55,716 KB
testcase_15 AC 125 ms
55,952 KB
testcase_16 AC 124 ms
55,768 KB
testcase_17 AC 122 ms
55,648 KB
testcase_18 AC 140 ms
56,372 KB
testcase_19 AC 141 ms
55,600 KB
testcase_20 AC 142 ms
55,388 KB
testcase_21 AC 143 ms
55,516 KB
testcase_22 AC 143 ms
55,768 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

package yukicoder.level2.no4;

import java.util.Scanner;

/**
 * [No.4 おもりと天秤](https://yukicoder.me/problems/19)<br>
 * 
 * 授業中にもかかわらず遊んでしまうdaveは、<br>
 * 理科の実験中に、色んな重さの種類があるおもりをすべて使って、<br>
 * ちょうど天秤が水平になるおもりの組み合わせがあるかを知りたくなったようで、それに遊び呆けてる。<br>
 * (すべてのおもりを使うため、余らせてはいけない。)<br>
 * <br>
 * あなたは、daveにその組み合わせがあるかどうか教えて、授業に集中させるようにしてください。<br>
 * <br>
 * もしそのような組み合わせがあれば possible 、なければ impossibleを出力してください。<br>
 */
public class WeightBalance {
	private static final String POSSIBLE = "possible";
	private static final String IMPOSSIBLE = "impossible";

	public static void main(String[] args) {
		new WeightBalance().execute();
	}

	private void execute() {
		int[] weights = read();

		boolean result = judgeBalanceable(weights);

		output(result);
	}

	/*
	 * 1.おもりの合計を出して、半分に分けられるかをチェックする
	 * 2.半分に分けられない場合はfalse分けられる場合は次に進む
	 * 3.今あるおもりの組み合わせで、おもりの合計の半分の値を作れるかどうかを判定する
	 *   →3は動的計画法を使う。
	 */

	boolean judgeBalanceable(int[] weights) {
		int sum = sum(weights);
		if(sum % 2 == 1) {
			return false;
		}
		int half = sum/2;
		return canCreateSum(half, weights);
	}

	//部分和問題を求めるロジック
	private boolean canCreateSum(int sum, int[] nums) {
		boolean[][] dpTable = new boolean[nums.length + 1][sum + 1];
		
		dpTable[0][0] = true;
		
		for(int i = 0; i < nums.length; i++) {
			for(int j = 0; j <= sum; j++) {
				if(nums[i] <= j) {
					dpTable[i + 1][j] = dpTable[i][j - nums[i]] || dpTable[i][j];
				} else {
					dpTable[i + 1][j] = dpTable[i][j];
				}
			}
		}
		return dpTable[nums.length][sum];
	}

	private int sum(int[] weights) {
		int sum = 0;
		for (int i = 0; i < weights.length; i++) {
			sum += weights[i];
		}
		return sum;
	}

	private int[] read() {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int[] weights = new int[num];
		for (int i = 0; i < num; i++) {
			weights[i] = sc.nextInt();
		}
		return weights;
	}

	private void output(boolean result) {
		System.out.println(result? POSSIBLE : IMPOSSIBLE);
	}
}
0