結果

問題 No.4 おもりと天秤
ユーザー ShotaroSuzuShotaroSuzu
提出日時 2020-07-02 15:10:03
言語 Java21
(openjdk 21)
結果
AC  
実行時間 159 ms / 5,000 ms
コード長 2,574 bytes
コンパイル時間 3,761 ms
コンパイル使用メモリ 77,544 KB
実行使用メモリ 41,976 KB
最終ジャッジ日時 2024-09-15 00:59:03
合計ジャッジ時間 8,129 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 135 ms
41,280 KB
testcase_01 AC 136 ms
41,172 KB
testcase_02 AC 137 ms
41,180 KB
testcase_03 AC 137 ms
41,400 KB
testcase_04 AC 135 ms
41,300 KB
testcase_05 AC 155 ms
41,976 KB
testcase_06 AC 136 ms
41,200 KB
testcase_07 AC 156 ms
41,604 KB
testcase_08 AC 148 ms
41,468 KB
testcase_09 AC 159 ms
41,676 KB
testcase_10 AC 158 ms
41,808 KB
testcase_11 AC 132 ms
41,336 KB
testcase_12 AC 131 ms
41,708 KB
testcase_13 AC 137 ms
41,192 KB
testcase_14 AC 135 ms
41,176 KB
testcase_15 AC 136 ms
41,048 KB
testcase_16 AC 136 ms
41,236 KB
testcase_17 AC 135 ms
40,984 KB
testcase_18 AC 156 ms
41,744 KB
testcase_19 AC 155 ms
41,728 KB
testcase_20 AC 155 ms
41,556 KB
testcase_21 AC 155 ms
41,960 KB
testcase_22 AC 157 ms
41,844 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